## Stable Sort

### March 23, 2018

A sorting algorithm is *stable* if items with equal keys appear in the output in the same order they appear in the input. In many cases the stability of a sorting algorithm doesn’t matter; in other cases it is critical. Some sorting algorithms, such as merge sort, are inherently stable (unless you muck up the implementation), which other sorting algorithms, such as quick sort, are inherently unstable. It is always possible to turn an unstable sort into a stable sort by adding an index to the data and using the index to break ties.

Your task is to write a program that converts an unstable sorting algorithm into a stable sorting algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Here’s a Haskell version. We write a sorting function that is guaranteed to be unstable, then apply a “stabilizing” function to it, resulting in a stable sort.

Here’s a solution in C (with the nested function GCC extension).

The data in the array to be sorted is not copied. Rather, arrays of indices and pointers are used. This approach seemingly complicated my solution, but would use less memory for large data types.

Output: