Sorting Algorithms

Let us assume that A is the array to be sorted. Also, let us say R and S have the same key and R appears earlier in the array than S. That means, R is at A[i] and S is at A[j], with i < j. To show any stable algorithm, in the sorted output R must precede S.

Lets examine the algorithms one by one.

1. Bubble sort:

Yes. Elements change order only when a smaller record follows a larger. Since S is not smaller than R it cannot precede it.

1. Selection sort:

No. It divides the array into sorted and unsorted portions and iteratively finds the minimum values in the unsorted portion. After finding a minimum x, if the algorithm moves x into the sorted portion of the array by means of a swap, then the element swapped could be R which then could be moved behind S. This would invert the positions of R and S, so in general it is not stable. If swapping is avoided, it could be made stable but the cost in time would probably be very significant.

1. Insertion sort:

Yes. As presented, when S is to be inserted into sorted subarray A[1, ..... , j – 1], only records larger than S are shifted. Thus R would not be shifted during S’s insertion and hence would always precede it.

1. Merge sort:

Yes. In the case of records with equal keys, the record in the left subarray gets preference. Those are the records that came first in the unsorted array. As a result, they will precede later records with the same key.

1. Heap sort:

No. Suppose i = 1 and R and S happen to be the two records with the largest keys in the input. Then R will remain in location 1 after the array is heapified, and will be placed in location n in the first iteration of Heapsort. Thus S will precede R in the output.

6.Quick sort:

No. The partitioning step can swap the location of records many times, and thus two records with equal keys could swap position in the final output.