Measures of Disorder and Straight Insertion Sort with Erroneous Comparisons

Abstract

In this paper, we analyze the familiar straight insertion sort algorithm and quantify the deviation of the output from the correct sorted order if the outcomes of one or more comparisons are in error. The disarray in the output sequence is quantified by six measures. For input sequences whose length is large compared to the number of errors, a comparison is made between the robustness to errors of bubble sort and the robustness to errors of straight insertion sort. In addition to analyzing the behaviour of straight insertion sort, we review some inequalities among the various measures of disarray, and prove some new ones.