Question

A sorting method is stable if for any i<j such that initially E[i] = E[j], the sort moves E[i] to E[k] and moves E[j] to E[m] for some k and m such that k < m. Which of the following algorithms are stable? For each that is not, give an example in which relative order of two equal keys is changed.

Insertion Sort

Maxsort

QuickSort

Heapsort

MergeSort

Radix Sort

Answer 1

from the given sorting techniques Insertion Sort, Max Sort and Radix Sort are stable .

Note:- In merge sort stablity is depends on the merge algorithm that is implemented as a part of the merge sort algorithm.

Heap sort unstable example

Consider array 21 20a 20b 12 11 8 7 (already in max-heap format)

here 20a = 20b just to differentiate the order we represent them as 20a and 20b

While heapsort first 21 is removed and placed in the last index then 20a is removed and placed in last but one index and 20b in the last but two index so after heap sort the array looks like

7 8 11 12 20b 20a 21.

It does not preserve the order of elements and hence can't be stable

Quick sort unstable example

Quick Sort is not stable because it swaps non-adjacent elements.

The most succinct example:

Given [2, 2, 1], the ‘2’ values will not retain their initial order.

Merge sort unstable example

It depends on the merge algorithm that is implemented as a part of the merge sort algorithm.

def merge(L,R):

i = 0

j = 0

answer = []

while i<len(L) and j<len(R):

if L[i]<=R[j]:

answer.append(L[i])

i += 1

else:

answer.append(R[j])

j += 1

if i<len(L):

answer.extend(L[i:])

if j<len(R):

answer.extend(R[j:])

return answer

print merge([1,1,2],[1,1,1,2,3])

but if you changed the 6th line to be -> if L[i]<R[j]
then the merge sort implemented by your algo would become unstable.