Stable, efficient sort?

Merge sort can be written to be in-place I believe. That may be the best route.

Note: standard quicksort is not O(n log n) ! In the worst case, it can take up to O(n^2) time. The problem is that you might pivot on an element which is far from the median, so that your recursive calls are highly unbalanced.

There is a way to combat this, which is to carefully pick a median which is guaranteed, or at least very likely, to be close to the median. It is surprising that you can actually find the exact median in linear time, although in your case it sounds like you care about speed so I would not suggest this.

I think the most practical approach is to implement a stable quicksort (it's easy to keep stable) but use the median of 5 random values as the pivot at each step. This makes it highly unlikely that you'll have a slow sort, and is stable.

By the way, merge sort can be done in-place, although it's tricky to do both in-place and stable.

There's a list of sort algorithms on Wikipedia. It includes categorization by execution time, stability, and allocation.

Your best bet is probably going to be modifying an efficient unstable sort to be stable, thereby making it less efficient.

What about quicksort?

Exchange can do that too, might be more "stable" by your terms, but quicksort is faster.

There is a class of stable in-place merge algorithms, although they are complicated and linear with a rather high constant hidden in the O(n). To learn more, have a look at this article, and its bibliography.

Edit: the merge phase is linear, thus the mergesort is nlog_n.

Because your elements are in an array (rather than, say, a linked list) you have some information about their original order available to you in the array indices themselves. You can take advantage of this by writing your sort and comparison functions to be aware of the indices:

function cmp( ar, idx1, idx2 )
{
   // first compare elements as usual
   rc = (ar[idx1]<ar[idx2]) ? -1 : ( (ar[idx1]>ar[idx2]) ? 1 : 0 );

   // if the elements are identical, then compare their positions
   if( rc != 0 )
      rc = (idx1<idx2) ? -1 : ((idx1>idx2) ? 1 : 0);

   return rc; 
}

This technique can be used to make any sort stable, as long as the sort ONLY performs element swaps. The indices of elements will change, but the relative order of identical elements will stay the same, so the sort remains robust. It won't work out of the box for a sort like heapsort because the original heapification "throws away" the relative ordering, though you might be able to adapt the idea to other sorts.

Quicksort can be made stable reasonably easy simply by having an sequence field added to each record, initializing it to the index before sorting and using it as the least significant part of the sort key.

This has a slightly adverse effect on the time taken but it doesn't affect the time complexity of the algorithm. It also has a minimal storage cost overhead for each record, but that rarely matters until you get very large numbers of records (and is mimimized with larger record sizes).

I've used this method with C's qsort() function to avoid writing my own. Each record has a 32-bit integer added and populated with the starting sequence number before calling qsort().

Then the comparison function checked the keys and the sequence (this guarantees there are no duplicate keys), turning the quicksort into a stable one. I recall that it still outperformed the inherently stable mergesort for the data sets I was using.

Your mileage may vary, so always remember: Measure, don't guess!

There's a nice list of sorting functions on wikipedia that can help you find whatever type of sorting function you're after.

For example, to address your specific question, it looks like an in-place merge sort is what you want.

However, you might also want to take a look at strand sort, it's got some very interesting properties.

Quicksort can be made stable by doing it on a linked list. This costs n to pick random or median of 3 pivots but with a very small constant (list traversal).

By splitting the list and ensuring that the left list is sorted so same values go left and the right list is sorted so the same values go right, the sort will be implicity stable for no real extra cost. Also, since this deals with assignment rather than swapping, I think the speed might actually be slightly better than a quick sort on an array since there's only a single write.

So in conclusion, list up all your items and run quicksort on a list

Perhaps shell sort? If I recall my data structures course correctly, it tended to be stable, but it's worse case time is O(n log^2 n), although it performs O(n) on almost sorted data. It's based on insertion sort, so it sorts in place.

Don't worry too much about O(n log n) until you can demonstrate that it matters. If you can find an O(n^2) algorithm with a drastically lower constant, go for it!

The general worst-case scenario is not relevant if your data is highly constrained.

In short: Run some test.

I have implemented a stable in-place quicksort and a stable in-place merge sort. The merge sort is a bit faster, and guaranteed to work in O(n*log(n)^2), but not the quicksort. Both use O(log(n)) space. A slightly shorter version of the stable merge sort is:

public class MergeSort<T> {
    public static <T> void sort(T[] data, Comparator<T> comp) {
        sort(data, comp, 0, data.length);
    }
    private static <T> void sort(T[] d, Comparator<T> comp, int from, int to) {
        if (to - from < 30) {
            InsertionSort.insertionSort(d, from, to - 1, comp);
            return;
        }
        int mid = from + (to - from) / 2;
        sort(d, comp, from, mid);
        sort(d, comp, mid, to);
        merge(d, comp, from, mid, to, mid - from, to - mid);
    }
    private static <T> int binarySearch(T[] d, Comparator<T> comp, int from, int to, int val, int smaller) {
        int len = to - from;
        while (len > 0) {
            int half = len / 2;
            int mid = from + half;
            if (comp.compare(d[mid], d[val]) < smaller) {
                from = mid + 1;
                len = len - half - 1;
            } else {
                len = half;
            }
        }
        return from;
    }
    private static <T> void reverse(T[] d, int from, int to) {
        while (from < to) {
            swap(d, from++, to--);
        }
    }
    private static <T> void merge(T[] d, Comparator<T> comp, int from, int pivot, int to, int len1, int len2) {
        if (len1 == 0 || len2 == 0) {
            return;
        }
        if (len1 + len2 == 2) {
            if (comp.compare(d[pivot], d[from]) < 0) {
                swap(d, pivot, from);
            }
            return;
        }
        int len1b = len1 / 2;
        int len2b = len2 / 2;
        int firstCut = from + len1b;
        int secondCut = pivot + len2b;
        if (len1 > len2) {
            secondCut = binarySearch(d, comp, pivot, to, firstCut, 0);
            len2b = secondCut - pivot;
        } else {
            firstCut = binarySearch(d, comp, from, pivot, secondCut, 1);
            len1b = firstCut - from;
        }
        if (firstCut != pivot && pivot != secondCut) {
            reverse(d, firstCut, pivot - 1);
            reverse(d, pivot, secondCut - 1);
            reverse(d, firstCut, secondCut - 1);
        }
        int mid = firstCut + len2b;
        merge(d, comp, from, firstCut, mid, len1b, len2b);
        merge(d, comp, mid, secondCut, to, len1 - len1b, len2 - len2b);
    }
    private static <T> void swap(T[] d, int i, int j) {
        T temp = d[i];
        d[i] = d[j];
        d[j] = temp;
    }
}

Maybe I'm in a bit of a rut, but I like hand-coded merge sort. It's simple, stable, and well-behaved. The additional temporary storage it needs is only N*sizeof(int), which isn't too bad.