100
200
300
400
500
600
700
800
900
Records
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
2
2.2
2.4
2.6
Time
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Bubblesort (direct)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Bubblesort (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
ShellSort (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Straight Insertion (direct)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Straight Insertion (indexed)
Introduction
- I'm building an eclectic sorting library which lets you choose the sort
routines you like (and even switch between them for different columns of the
data you're sorting). So far I've built in 14 different types of sort
algorithm. I plan to add quite a few more before I'm done. At least:
- Versions of Shellsort, Heapsort, and
Straight Merge that directly sort
the key values rather than their indices (Heapsort and Shellsort should
double in speed, Straight Merge will probably only get better by 30%).
Heapsort should then be able to give Quicksort a run for its money.
- A balanced tree sort (this may be faster yet);
- A distribution sort (good when you know all the values you can possibly get)
- A mixed insertion/distribution sort (good when you know there are only
a few possible values, but not what they are);
- A radix sort (which will suck for small N but work wonders for large N)
- I've also got a page that discusses why I'm breaking with tradition
and building sorts that work on actual sort column values rather than indices
(speed! and I've found a way to get away with it!), and talks about a few
other things besides (like case conversion, nulls, and descending sort orders,
and how I think they should be dealt with).
- Lastly, there's another page of graphs where I analyze, in more detail,
the raw data shown in the graphs here, and chat about the pros and cons of
various "pre-sort" and "post-sort" checks and
conversions I think are worthwhile (case, descending order, nulls)
(and shows why I think they don't actually belong in
sort algorithms themselves)
- This page doesn't work well on small monitors. Sorry about that!
Nothing I can do about it - my graphing engine can't build
graphs that dynamically resize to fit your screen... yet. I'll have
to port from server to client for that!
- Don't worry! When I finally finish the sorting library to my
satisfaction I'll publish it as a zip file on this site.
But don't hold your breath. The List Mergesort routine
has a bug that shows up about 10% of the time at 20,000 records or more.
I only add an average of two sort routines a day and I haven't even started
on the classes that will let you chop and change, using multiple sort
algorithms to sort different columns (or even partitions of the
same column) within the same sort call.
- It will allow you to plug in new sort algorithms at run-time (and
automate testing of same - that's how I know about the List Merge bug).
- It makes life easy for your sort code. No null checks. No worrying about
case. No doing descending order. All that is handled for all
sorting routines. To give you an idea, my two Insertion Sort routines
come to <120 lines of code, comments and all.
The Graphs
I had been planning to graph response times of the various sort routines,
one against another. But it doesn't work. The times for Insertion Sort,
Bubblesort and Shell Sort are so much worse you have to use logarithmic
graphs to make them even look like they compete with the others. As the
next two graphs show. We can see from this graph that Bubblesort is really
awful, Straight Insertion awful, and Shell Sort is merely bad.
100
200
300
400
500
600
700
800
900
Records
0.005
9.99999999999999E-03
0.015
0.02
0.025
0.03
0.035
0.04
0.045
0.05
0.055
0.06
0.065
0.07
7.49999999999999E-02
7.99999999999999E-02
8.49999999999999E-02
Time
X
X
X
X
X
Bubblesort (direct)
X
X
X
X
Bubblesort (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Heapsort (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
List Mergesort (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Quicksort (0R) (direct)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Quicksort (0R) (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Quicksort (2R) (direct)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Quicksort (2R) (indexed)
X
X
X
X
X
X
Quicksort (3-way) (direct)
X
X
X
X
X
X
Quicksort (3-way) (indexed)
X
X
X
X
X
X
X
ShellSort (indexed)
X
X
X
X
X
X
X
Straight Insertion (direct)
X
X
X
X
X
X
X
Straight Insertion (indexed)
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Straight Mergesort (indexed)
The next few graphs indicate how various different sorting algorithms respond
to different sorts of sort data. The first row shows, for each of three sorting
algorithms, their response curves for ten different sorts of input.
| Quicksort (passive swaps) |
|
200
400
600
800
Records
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
0.22
0.24
0.26
Time
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
200
400
600
800
Records
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
Time
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
200
400
600
800
Records
0.005
9.99999999999999E-03
0.015
0.02
0.025
0.03
0.035
0.04
0.045
Time
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
200
400
600
800
Records
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
0.09
Time
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
200
400
600
800
Records
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
Time
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
O
200
400
600
800
Records
0.01
0.02
0.03
0.04
0.05
0.06
0.07
0.08
Time
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
200
400
600
800
Records
0.005
9.99999999999999E-03
0.015
0.02
0.025
0.03
0.035
0.04
0.045
0.05
0.055
0.06
0.065
Time
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
200
400
600
800
Records
0.02
0.04
0.06
0.08
0.1
0.12
0.14
0.16
0.18
0.2
Time
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
Example of a sort algorithm, warts and all
'
'...from the clsInsertionSort class...
'
Private Function ISortAlgorithm_SortDirect(ByVal L As Long, ByVal R As Long, ByRef D) As Boolean
'
'Parameters: L - Left hand index into partition of array that is to be insertion sorted
' R - right hand index into partition of array that is to be insertion sorted
' records between indices (L) and (R) will be compared.
' D - The array for which a partition is to be insertion sorted.
'Assumptions: lbound(d)<=L<=R<=ubound(d). d Contains no Nulls. d Contains no Objects
'
Dim j As Long 'index when searching for inversions
Dim i As Long 'index when correcting inversions
Dim v As Variant 'value of element on the move
Dim oldI As Long 'index of element being moved
For j = L + 1 To R
If D(j) < D(j - 1) Then 'If this element is out of order
i = j - 1 'Search backwards for the most recent element
v = D(j) 'that belongs before it, shuffling records
Do 'forward to make room so we can insert it
D(i + 1) = D(i) 'in the right spot.
i = i - 1
If i < L Then Exit Do 'because we don't know we have a magic low value at
Loop 'the bottom of the array
D(i + 1) = v 'Put the element where it belongs
End If
Next '...and continue where we we left off.
'We know elements (L) through (J) are sorted.
ISortAlgorithm_SortDirect = True
End Function
Okay, so that's a crumby routine (it takes O(N*N) steps to sort an array of N elements, on
average). But that code is what sorts the little partitions (<9 elements) at the
end of the Quicksort that is currently winning. It may be a bad way to sort a big array
of totally unsorted elements, but it's a great way smooth out the last few kinks and
finish off the job for Quicksort (or to smooth the path for a Straight Merge, too).
