Which of the following sorting algorithms are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
Insertion sort is stable. When inserting an element into the sorted portion, we stop as soon as we find an element that is less than or equal to (not just less than) the element being inserted. This preserves the relative order of equal elements.
Merge sort is stable. During the merge operation, when elements from both halves are equal, we take from the left subarray first. Since the left subarray contains elements that appeared earlier in the original array, this preserves relative order.
Heapsort is not stable. The heap operations can change the relative order of equal elements. For example, with input \([2, 2']\), heapify operations might place \(2'\) before \(2\) in the internal representation, causing them to be extracted in reverse order.
Quicksort is not stable. The partitioning step can swap equal elements in ways that reverse their relative order. When the pivot equals some elements, those elements might end up on either side of the pivot position, disrupting their original ordering.
To make any sorting algorithm stable, add a unique index to each element as a secondary key. Create pairs \((A[i], i)\) for each element in \(\Theta(n)\) time and \(\Theta(n)\) space. When comparing elements, use the original values first, and break ties by comparing indices: \((x, i) < (y, j)\) if \(x < y\), or if \(x = y\) and \(i < j\). After sorting, extract just the values in \(\Theta(n)\) time.
This guarantees stability because when values are equal, we break ties using the original position. The cost is \(\Theta(n)\) additional space for the indices and \(\Theta(n)\) additional time for pre/postprocessing (asymptotically no change for most algorithms).