Recursive merge sort with erroneous comparisons

In this paper, we analyze the recursive merge 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 disorder in the output sequence is quantified by four measures: the number of runs, the smallest number of integers that need to be removed to leave the sequence sorted, the number of inversions, and the smallest number of successive exchanges needed to sort the sequence. 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, straight insertion sort, and recursive merge sort.

► We analyze the merge sort algorithm when outcomes of comparisons are in error.
► We quantify the deviation of the output sequence from the correct sorted order.
► The disorder in the output sequence is quantified by four measures of disarray.
► We compare the robustness of this sort algorithm to errors with other algorithms.