Fastest In-Place Stable Sort

Download source - 34.89 KB

Introduction

If you need a stable sorting algorithm that is fast and does not need extra storage space of O(N) then you should go straight past the usual O(N^2) sorts like Insertion Sort, Selection Sort and Bubble Sort. This application contains 2 in-place stable sorts that are much faster:

In-Place Merge Sort
Stable Quick Sort

This application demonstrates both algorithms and compares them with:

Insertion Sort which is also stable and in-place
Traditional Merge Sort which is stable but required O(N) extra storage
Traditional Quick Sort which is not stable but is in place.

Background - In Place Merge Sort

I took the algorithm for In Place Merge Sort from Thomas Baudel's version. It sorts in the same way that a merge sort does except the merge process is in-place. It is very fast and elegant and uses O(logN) extra space. The extra effort in maintaining stability in-place makes it slower than most other O(NLogN) sorts but speed is still in the same order of magnitude.

Background - Stable Quick Sort

This algorithm sorts in the same way that Quick Sort does. The difference is that the pivot function doesn't just swap elements that need to be moved. Instead, it builds up lists of runs in a buffer. Whenever the buffer is full, it accumulates the runs in a binary pattern. This algorithm is about 20% faster than In-Place Merge Sort but it is not as elegant. It also uses O(logN) extra space. The extra effort in maintaining stability in-place also makes it slower than most other O(NLogN) sorts but speed is still in the same order of magnitude.

Using the Code

The download includes an executable that demonstrates the sorts. Other than that, the sort is contained in one module.

Points of Interest

I attempted several things before this version:

I made a stable version of heap sort (it ran in O(n^2) time).
I made a version of in-place merge using the run buffers but could not get it to be as fast as Thomas's version.