Array Sorting

by Malcolm Phillips

< Back to Sorting

bullet Exchanging Sort Techniques
bullet Selection Sort Techniques
bullet Insertion Sort Techniques
bullet Merge Sort Techniques
bullet Tree Sort Techniques
bullet Heap Sort Techniques
bullet Quick Sort Techniques
bullet Oddball Techniques
bullet Non-Comparison-Based Sort Techniques
bullet Unfeasible Sort Techniques

Okay, let's assume that you're going to be doing internal, sequential sorting, in place, on an array. There are tons of algorithms to choose from, and although many of them are faster than others in general, for most sorting algorithms there does exist a situation where a particular algorithm is a better choice than any other. First of all, many of the algorithms below make use of “Swap”. This can be a function or a macro, whose sole purpose is to swap two items from anywhere in memory.
One such definition for this is:
[show source code]
I'll also present a few other necessary odds and ends used by some algorithms:
[show source code]

Exchanging Sort Techniques

Bubble Sort


Probably the most well-known sorting algorithm is bubble-sort. In bubble sort, the values float one at a time to the end of the array, slowly moving one item into position each pass. The code consists of two loops, a compare, and a swap (of adjacent items). Bubble Sort is stable because it only ever swaps adjacent items, and only if the first one is strictly greater than the second one. Sometimes people implement Simple Sort, thinking they have actually implemented Bubble Sort, but if it doesn't always compare adjacent items, it isn't Bubble Sort. Depending on the order of the for-loops this is sometimes called Sink Sort.

Example with random numbers:
    Initial list: 17, 37, 48, 29, 13, 42, 50, 4, 63
First outer loop pass (swaps in red, comparisons not resulting a swap are omitted):
    Swap: 17, 37, 29, 48, 13, 42, 50, 4, 63
    Swap: 17, 37, 29, 13, 48, 42, 50, 4, 63
    Swap: 17, 37, 29, 13, 42, 48, 50, 4, 63
    Swap: 17, 37, 29, 13, 42, 48, 4, 50, 63
Second outer loop pass:
    Swap: 17, 29, 37, 13, 42, 48, 4, 50, 63
    Swap: 17, 29, 13, 37, 42, 48, 4, 50, 63
    Swap: 17, 29, 13, 37, 42, 4, 48, 50, 63
Third outer loop pass:
    Swap: 17, 13, 29, 37, 42, 4, 48, 50, 63
    Swap: 17, 13, 29, 37, 4, 42, 48, 50, 63
Fourth outer loop pass:
    Swap: 13, 17, 29, 37, 4, 42, 48, 50, 63
    Swap: 13, 17, 29, 4, 37, 42, 48, 50, 63
Fifth outer loop pass:
    Swap: 13, 17, 4, 29, 37, 42, 48, 50, 63
Sixth outer loop pass:
    Swap: 13, 4, 17, 29, 37, 42, 48, 50, 63
Seventh outer loop pass:
    Swap: 4, 13, 17, 29, 37, 42, 48, 50, 63
As you can see, some items take a long time to reach their destination (like the 4 above) because they can only move one position for each outer loop pass. These are called turtles, and are the main speed problem with Bubble Sort. Items moving in the other direction move fast (like 48 above) and are called hares.

[show source code]

http://en.wikipedia.org/wiki/Bubble_sort
http://xlinux.nist.gov/dads/HTML/bubblesort.html

Improved Bubble Sort
Bubble sort can be improved by keeping track of whether or not a swap is made on each inner loop pass, and if not, then the sorting is completed. This means adding a set, a clear, and a test of a flag variable to the code. Now, if the array is already sorted or nearly sorted, then the inner loop only runs once, or only a few times. Improved Bubble Sort is still stable as it still only swaps adjacent items and only if the first one is strictly greater than the second one.

[show source code]

http://www.sorting-algorithms.com/bubble-sort

Best Bubble Sort
The improvement to Bubble Sort above can be taken further. After each pass we have moved the highest misplaced item to its correct spot. This means that further bubbles will never need to be bubbled up past this point. If that point is the first item in the array, then we are done. So this acts much like the first improved version, but is even better if the last few items are already in position.
Again, this is still Bubble Sort, and so is stable.

[show source code]

Simple Sort (Substitution Sort)
Perhaps the easiest algorithm to implement is simple sort. In simple sort, the code consists of two loops that compare every item to every other item, and a swap if they are out of order. The inner loop can either start just after the outer loop, or an extra test can be added to check that the inner loop position is greater than the outer one.
Unlike Bubble Sort, this algorithm is NOT stable.

[show source code]

http://www.sortieralgorithmen.de/simplesort/index.html

Shaker Sort


Also called "Cocktail Sort". There are some algorithms based on Bubble Sort, which improve the algorithm somewhat. For example Shaker Sort, which performs Bubble Sort, passes in alternating directions. The alternating passes mean many items repeatedly move back and forth from one spot, to the next spot over, and then back to the first spot, giving a noticeable shaking effect if animated. This allows both small and large items to move towards their destination, as the algorithm progresses.
Shaker Sort is stable.

[show source code]

http://en.wikipedia.org/wiki/Shaker_sort
http://xlinux.nist.gov/dads/HTML/shakerSort.html

Odd Even Transposition Sort


Also called "Brick sort". Another algorithm is to alternately swap the even items with their next item for one pass, and then the odd items with their next item for the next pass. This allows both large and small items to go towards their destination as we progress too. It is similar to Shaker Sort and Improved Bubble Sort, but doesn’t have a way of stopping early. The good news is that the algorithm lends itself well to parallelisation because all of the compare-and-swap operations in each pass could theoretically be performed at once. Multi-core CPUs could be utilised to do this, but perhaps to very little advantage since there are many asymptotically faster algorithms anyway.
Odd Even Transposition Sort is stable.

[show source code]

http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html

Several-Unique Sort
An interesting variation of Bubble Sort was obtained by a genetic algorithm known as '"Critticall". That's right; a computer learned a better algorithm. The change was to make all items equal to the current bubble, float up with it. This was called Several-Unique Sort, because it works well when there are several instances of each item (i.e. duplicates), but it is otherwise slightly slower than bubble sort.
Several Unique Sort is NOT stable.

[show source code]

http://www.critticall.com/sort.html

Comb Sort
The most effective way to improve bubble sort is to allow the gap between items compared to vary. Start off high and then decrease, in the same way that if your hair was really knotted you wouldn't reach for you finest toothed comb first. You'd probably use a comb with big teeth first to get out the big knots, and then use a finer comb. This is exactly what comb sort does.
Many people have tried different shrink factors other than 1.3 with this algorithm, and there are even lists of hand-optimised gap tables out there. But I still find that it’s very hard to beat the factor of 1.3 and the special modification to prevent gaps of nine or ten (known as combSort11), by any significant amount, and some other gap-tables are actually slower. The same early-exit trick of improved bubble sort is also utilised here.
Comb sort is NOT stable.

[show source code]

http://en.wikipedia.org/wiki/Comb_sort
http://xlinux.nist.gov/dads/HTML/combSort.html

HBubbleSort

The same technique as is used in Shell Sort (see further down the page) can be used with Bubble Sort. Each pass consists of a bubble sort pass, instead of an insertion pass as would be done in Shell Sort. This algorithm is rarely used as it exists mostly to demonstrate that the principle used in Shell Sort can be used independently of the H-Sorting algorithm used.
Like Shell Sort, H-Bubble Sort is NOT stable.

[show source code]

http://www.cs.princeton.edu/~rs/shell/paperF.pdf

HShakeSort

The same technique as is used in Shell Sort (see further down the page) can be used with Shaker Sort. Each pass consists of a upwards and a downwards shaker sort pass, instead of an insertion pass as would be done in Shell Sort. This algorithm is also rarely used as it exists mostly to demonstrate that the principle used in Shell Sort can be used independently of the H-Sorting algorithm used.
Like Shell Sort, H-Shake Sort is NOT stable.

[show source code]

http://www.cs.princeton.edu/~rs/shell/paperF.pdf

HBrickSort

The same technique as is used in Shell Sort (see further down the page) can be used with Brick Sort. Each pass consists of an odd and an even brick sort pass, instead of an insertion pass as would be done in Shell Sort. This algorithm is also rarely used as it exists mostly to demonstrate that the principle used in Shell Sort can be used independently of the H-Sorting algorithm used.
Like Shell Sort, H-Brick Sort is NOT stable.

[show source code]

http://www.cs.princeton.edu/~rs/shell/paperF.pdf

Selection Sort Techniques

Selection Sort


Another basic sorting strategy is to simply search for the next largest (or smallest if you prefer) item on each pass and move it into position. This gives the advantage that we only need to perform one swap on each pass, making it much better in terms of less copying, but performing the same number of comparisons. At first one might think this would make a huge speed difference, but in reality it often doesn't make that much difference. This algorithm is called Selection Sort.
Selection Sort on an array is NOT stable because in order to place an item in its final spot, we move the item that was there to somewhere that might be before some other item that was equal to it, thus reversing the order of items that were equal (if you follow).

[show source code]

http://en.wikipedia.org/wiki/Selection_sort
http://xlinux.nist.gov/dads/HTML/selectionSort.html

Dual Selection Sort
In an effort to further reduce copying, and reduce the number of passes, you can of course search for the next smallest and next largest item on each pass, and move both into position. There is a special case you have to deal with though, when the largest item is already where you want the smallest one to go. Even with the attempted improvements, it most likely not going to be significantly faster than standard selection sort. Dual Selection sort on an array is also NOT stable.

[show source code]

http://warp.povusers.org/DoubleBurstSelectionSort/
http://www.softpanorama.org/Algorithms/Sorting/selection_sort.shtml

Bingo Sort
As with Several Unique Sort, we can write a selection style algorithm, which will take advantage of there being many duplicates. After finding the largest item, you perform another pass to move any other items equal to the max item to their final place. This means less passes than Selection Sort if there are on average more than 2 of each item, otherwise the extra loops only slows things down.
Bingo Sort on an array is NOT stable for the same reason as Selection Sort.

[show source code]

http://xlinux.nist.gov/dads/HTML/bingosort.html

Exact Sort
Exact Sort is a form of Selection Sort with a difference. Usually after finding the nth smallest item you swap it with the nth item in the array. However the item that was previously at the nth position gets moved to some other location, which probably isn't its final resting position. Consequently each item ends up getting moved almost twice on average. This algorithm goes to the extreme to further reduce unnecessary item copying. In this algorithm, before an item is placed in its final resting position, the one that was in its spot is first relocated to its final resting position, and before that, the one there must be moved to its final resting position, and before that… well you get the picture. Suffice to say, each item is only moved once. This is except of course, for the item that is removed first and put back at the end, so that you have room to move the rest around. One would only want to use this algorithm if moving an item was extremely expensive (slow) for some reason. E.g. you might do this when rearranging furniture. First work out the way or ordering things using the least moves, and then follow that plan.
Exact sort is NOT stable.

[show source code]

http://www.geocities.com/p356spt/

Insertion Sort Techniques

Insertion Sort


Another well known sorting technique is Insertion Sort. During Insertion Sort, you always have a sorted portion and an unsorted portion. Initially the sorted portion consists of only 1 item. Each subsequent step involves finding a place in the sorted portion for a single item from the unsorted portion, and inserting that item into the sorted portion. Thus enlarging the sorted portion and shrinking the unsorted portion, until the unsorted portion becomes empty. At that point, the entire thing is sorted. An unfortunate downside to this technique is that Inserting the item usually means moving many items over to make room for it. Usually the search starts from the position just to the right of where the unsorted item lies, such that if the array is already sorted, it is very fast to insert. I prefer to first test if the item to be inserted actually needs any moving at all, and if not (i.e. it comes after all items in the sorted portion), we simply extend the sorted portion to include this item, and don't move anything. In fact, this is among the fastest algorithms for sorting an almost sorted array. When it is completely sorted, there are O(n) compares and no swaps. That's the same amount of work as testing if an array is sorted already! However if the array starts off in reverse order, it will be very slow because many moves and many comparisons will be required. Note: Moving items over to make room for insertion, can be done by means of repeated swapping; however I prefer to simply remember the value to insert, move the required items all over by one, and then place the remembered item into the hole.
Insertion sort is stable.

[show source code]

http://en.wikipedia.org/wiki/Insertion_sort
http://xlinux.nist.gov/dads/HTML/insertionSort.html

Dual Insertion Sort
Insertion sort, like bubble sort can be improved in various ways. The main problem with it is that it takes so long to move items over in memory to make space for the item to be inserted. One (not so effective) way to reduce this is to store two sorted portions, on at the end of the array, and one at the beginning. This means that one you've worked out which end to insert into; there are half as many moves required for inserting it. As things progress, having to move on average half the number of items to perform an insert begins to halve the time taken to sort. However the size of the sorted portions needs to occasionally be balanced as well, by performing an extra swap occasionally to transfer items from the end of the larger sorted portion onto the smaller portion. For a large number of items this modified algorithm might cut the time taken by perhaps almost 50%, which is not that fantastic since a large array can be sorted much faster using other techniques anyway. You could say that this 'optimisation' is beating a dead horse, but in a way it is a step towards the Library Sort algorithm mentioned further on.

As far as I am aware, this algorithm is my own creation. Therefore I do not yet have any links to other sites with the algorithm. Furthermore its usefulness is extremely low anyway, as it is rather large and not significantly faster than insertion sort.

[show source code]

Binary Insertion Sort
Another way to speed insertion sort up a little, is to perform a binary search to find the place to insert. Although most of the time is spent moving items along to make space, the searching phase for each item can be significantly improved (especially over the reverse sorted case) by performing a binary search. The trade-off is that the already sorted case will be slower, because it will take n*log(n) compares instead of just n, but the average case will improve somewhat.
Binary Insertion sort can be stable if written carefully, as shown.

[show source code]

http://en.wikipedia.org/wiki/Insertion_sort
http://xlinux.nist.gov/dads/HTML/binaryinsort.html

Interpolation Insertion Sort
Another way to search for the insertion point is by successive approximations using interpolation search. Basically you calculate about where the insert should go, and then see if your estimate was too high or too low and make another linearly interpolated guess. This is very much like binary searching, but can often be faster. However this also requires that the items at the very least, also support being subtracted. That means Either being a built-in type, or having a subtraction operator defined in addition to the less-than operator. This is therefore not a comparison-based sorting algorithm.
Interpolation Insertion sort can also be stable if written carefully, as shown.

[show source code]

Strand Sort
Another way to improve upon the insertion technique is to identify runs of items in the array, and insert all of the items in the run in the same pass. This is the idea behind Strand sort. First measure the length of the ascending sequence, and then make a pass through the sorted portion to insert those items. The insertion pass for the run is actually the same as an in-place merge, which we'll come across later.
Strand sort is stable.

[show source code]

http://xlinux.nist.gov/dads/HTML/strandSort.html

Bidirectional Strand Sort
We can attempt to further enhance strand sort by allowing it to recognise reverse sorted strands too, flip those around then insert/merge them as per strand sort. This usually boosts the average sequence length. You could again say that this 'optimisation' is beating a dead horse though.
Bidirectional Strand Sort is stable if you only look for explicitly decreasing sequences before reversing them, as done here.

As far as I am aware, this algorithm is my own creation. Therefore I do not yet have any links to other sites with the algorithm. Furthermore its usefulness is extremely low anyway.

[show source code]

Order Sort
This algorithm is kind of a cross between array-based Insertion Sort and list-based Insertion Sort, that attempts to keep the advantages of both.
It uses an index list internally, allowing insertion into the sorted portion (of the index list) in constant time. However unlike list-based insertion sort, it can find the point of insertion in faster than O(n) time. This is done by sampling through the original array over some of the items that have already been inserted. Instead of examining half of them on average, it explicitly scans the square root of the number inserted so far at even intervals, and uses this as a best guess. From there it scans linearly forwards to find the real insertion point. Of m items already inserted, this samples sqrt(m) items initially, plus on average sqrt(m)/2 further items to find the real insertion point, assuming the initial sampling gave a close approximation. This leads to a typical execution time of about O(n1.5).
Just like list-based Insertion Sort, Order Sort is stable.

[show source code]

http://www.ddj.com/dept/cpp/184402000

Shell Merge Sort
Perhaps the best way to improve insertion sort is the same way we made comb sort such a huge improvement over bubble sort. We allow the sorted arrays to consist of items that are very spread out. I've called this Shell Merge Sort, because it has similarities to both Shell Sort and Merge Sort. In fact it performs basically the same as the original Shell Sort which halved the increment size after each pass, except that the order of the passes is different.
This sorting algorithm is NOT stable.

I have not seen Shell Sort written like this elsewhere. Therefore I do not yet have any links to other sites with the algorithm. Furthermore it has no advantage over normal Shell Sort, which does not use recursion.

[show source code]

Shell Sort


The other way to improve insertion sort is of course, Shell Sort invented by Donald Shell in 1959. Whereby the same principle as Comb Sort is used, except that the insertion method is used to k-sort the items on each pass. There are many variants of this algorithm alone, but basically they all just use different number sequences for the gap sizes in each pass. The Incerpj - Sedgewick sequence used here is currently regarded as the best and is about O(nlog2n), but there are a lot of other gap table variations out there. Of algorithms that use no extra heap or stack memory (recursive calls) this is among the fastest.
This sorting algorithm is NOT stable.

[show source code]

http://xlinux.nist.gov/dads/HTML/shellsort.html
http://www.research.att.com/~njas/sequences/A036569
http://www.cs.fiu.edu/~weiss/Shellsort.html

Hybrid Comb Sort
Comb Sort (mentioned at the end of the bubble-sort section) can be further sped up by switching to Insertion Sort when the comparison gap becomes small enough. This is called Hybrid Comb sort.
This sorting algorithm is NOT stable.

[show source code]

http://yagni.com/combsort/correspondence.php

Library Sort
There have been some recent developments which expand on the insertion method of sorting, such as Library Sort. The idea expands on Insertion Sort, and attempts to get around the problem of requiring so many moves to insert each item. It leaves holes in the target array so that it doesn't don't have to move many items when doing the insert. When the number of holes gets low, a special pass is done to spread the items out some more again. This implementation was created from a description of the algorithm, as I have never actually seen another implementation of it. As such, it might not be 100% as the authors (Michael A Bender, Martin Farach-Colton, Miguel Mosteiro 2006) intended it, but nevertheless it works well enough, even though this implementation is rather large.
The below implementation of this algorithm is NOT stable, though it should be able to be modified to be stable

[show source code]

http://en.wikipedia.org/wiki/Library_sort
http://www.cs.sunysb.edu/~bender/pub/FUN2004-librarysort.ps

Merge Sort Techniques

In-Place Merge Sort
Another way to sort is by using a technique known as merging. Using the process of induction, we can write a divide-and-conquer algorithm that splits the problem up into two smaller sequences, sorts those using the same algorithm and then merges those two to produce a larger sorted list, merely by removing the first item from the sequence with the lowest item each time and appending it onto the sorted sequence.
In-Place Merge Sort is stable.

[show source code]

http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

Bitonic Merge Sort
Unfortunately it doesn't turn out to be very easy to efficiently merge data 'in-place' in an array. We have a few options though. We could sort the second half in reverse, which at first seems counter-productive, but this novel idea allows us to actually sort it much faster without using extra memory. Note that despite what you may find another website saying, this idea only works for array sizes that are a power of two. The modification made by some to pretend that it is a power of two in size, but with the imaginary elements before the start all being equal, does not work. I have emailed the author of one site about this, showing that even in their own applet some cases will fail, but I have got no response. A common solution is to perform an Insertion Sort pass over the array afterwards if the size was not a power of two, as it will be mostly in order.

[show source code]

http://xlinux.nist.gov/dads/HTML/bitonicSort.html
http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm

Merge Sort
Although Merge Sort can be implemented without using extra memory, the merging process is either slow or complicated that way. A much faster or easier way to merge is to use extra memory for the merges. Merge Sort using a second buffer as a temporary only. Or better yet, merge from one buffer into another, then merge back again, as I've done below. Merge Sort is stable.

[show source code]

Breadth-First Merge Sort


Merge Sort is fairly recursive, and obviously it would be nice to not use so much stack space. With some effort we can translate the algorithm to its iterative 'breadth-first' form. However, doing this it seems quite difficult at first to deal with arrays that are not a power of two in size. No Problem, we just pretend it is a power of two, but ignore any items outside the actual range. We then treat the array as n sequences of length 1. We merge odd and even sub-arrays to produce n/2 sequences of length 2. Then we again merge odd and even sub-arrays to produce n/4 sequences of length 4, etc. Until finally we merge 2 sequences of length n/2 to complete the sorting.
Breadth-First Merge Sort is stable.

[show source code]

Breadth-First Bitonic Merge Sort


We could have used the same 'breadth-first' idea just mentioned back when we were doing bitonic merges too. Build tiny increasing and decreasing sequences and use bitonic merge on those until you have a single bitonic sequence, and then make that in to the first half of a bitonic sequence, conveniently known as a monotonic (i.e. sorted) sequence.

[show source code]

http://www.tools-of-computing.com/tc/CS/Sorts/bitonic_sort.htm

Semi-Breadth-First Bitonic Merge Sort
When first attempting to write this in its breadth-first form, I only made the inner loop breadth-first, not the outer one. This gives yet another distinct sorting pattern, and actually seemed to run faster than either of the other forms, so I kept it.

[show source code]

Natural Merge Sort
A different approach is to take advantage of and existing runs in the data, just like Strand sort did, and merge whatever runs happen to already be present in the sequence, rather than breaking it up into sequences at odd places. This is done by allocating extra memory twice the size of the original array. We logically split this extra memory into two buffers and are then free to dump runs of items in either buffer as appropriate. For every item from the input list that you examine, you copy the item into one of the output buffers according to the following rules:

1. If both of the next items in the input buffers are larger than the last item added to the output buffer: Append the one with the larger top value, keeping the average of the top values as low as possible, giving maximum chance of being able to further extend the run with the next item added.
2. If both of the next items in the input buffers are smaller than the last item added to the output buffer: Again, append it to the one with the larger top value, keeping the average of the top values as low as possible, making it more likely that the next item will be able to once again further extend the run.
3. If one of the next items in the input buffers is less than the last item added to the output buffer, and the other is greater: Append the one with the larger top value because that extends the run length whereas appending the one from the other buffer would not. This is important because otherwise run lengths will not increase very quickly and the sort would actually become O(n2).

Natural Merge Sort is NOT stable.

[show source code]

http://www.eternallyconfuzzled.com/tuts/algorithms/jsw_tut_sorting.aspx#merge

Continue with more Array Sorting >

Download Mega Sorting Demo program (104933 bytes zip file)