## Stable Sort

### March 23, 2018

Before we get started, we need some data that will demonstrate whether a sort is stable or unstable. Here is a list of pairs; the second elements of the pairs are in decreasing order. We also provide an ordering function that ignores the second elements of the pairs:

(define xs '( (alfa zulu) (bravo yankee) (charlie xray) (delta whiskey) (echo uniform) (alfa tango) (bravo sierra) (charlie romeo) (delta papa) (echo oscar)))

(define (lt? a b) (stringstring (car a)) (symbol->string (car b))))

Chez Scheme uses merge sort for its native sorting algorithm, and is stable. We need an unstable sorting algorithm for testing; here’s a naive quicksort, O(*n*²) on already-sorted data:

(define (qsort lt? xs) (if (or (null? xs) (null? (cdr xs))) xs (let ((pivot (car xs))) (let loop ((xs (cdr xs)) (lesser (list)) (equal-or-greater (list))) (if (null? xs) (append (qsort lt? lesser) (list pivot) (qsort lt? equal-or-greater)) (if (lt? (car xs) pivot) (loop (cdr xs) (cons (car xs) lesser) equal-or-greater) (loop (cdr xs) lesser (cons (car xs) equal-or-greater))))))))

You can see that `qsort`

is unstable; both *delta* and *echo* are in reverse order of their input:

> (qsort lt? xs) ((alfa zulu) (alfa tango) (bravo yankee) (bravo sierra) (charlie xray) (charlie romeo) (delta papa) (delta whiskey) (echo oscar) (echo uniform))

We are ready to show our stable-sorting wrapper. It’s arguments are a non-stable sorting algorithm, a less-than predicate, and a list to be sorted:

(define (stable-sort sort lt? xs) (define (less? a b) (or (lt? (cadr a) (cadr b)) (and (not (lt? (cadr b) (cadr a))) (< (car a) (car b))))) (map cadr (sort less? (zip (range (length xs)) xs))))

`Zip`

augments each data item with the index at which it appears in the input, `sort`

calls the unstable sorting algorithm with a special ordering predicate, and `map`

removes the index. The `less?`

predicate uses `lt?`

unless the two items compare equal, in which case it compares the initial indexes of the two items.

You can see that the sort is stable; at each pair of identical first elements, the second elements are in decreasing order, including *delta* and *echo*:

> (stable-sort qsort lt? xs) ((alfa zulu) (alfa tango) (bravo yankee) (bravo sierra) (charlie xray) (charlie romeo) (delta whiskey) (delta papa) (echo uniform) (echo oscar))

You can run the program at https://ideone.com/x5cN53.

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: