Excel Sort() Algorithm

M

Michael C

Someone raised a question in my computer class. Does anyone know what type
of sort algorithm Excel uses when you highlight a range and hit the sort
button? I suspect it's not a Bubble sort, because of the inefficiency
involved, but beyond that I don't know what type of sort algorithm they
would have implemented.

Thanks,
Michael C.
 
A

Amedee Van Gasse

Michael said:
Someone raised a question in my computer class. Does anyone know
what type of sort algorithm Excel uses when you highlight a range and
hit the sort button? I suspect it's not a Bubble sort, because of
the inefficiency involved, but beyond that I don't know what type of
sort algorithm they would have implemented.

Thanks,
Michael C.
Click to expand...

I don't know, but John Walkenbach compares a few sorting algorithms in
Excel (version) Power Programming pages 321-323:

Table 11-1
Sorting Times in Seconds for Four Sort Algorithms
Using Randomly Filled Arrays

Array Excel Worksheet VBA Bubble VBA Quick VBA Counting
Elements Sort Sort Sort Sort
100 0.05 0.00 0.05 0.00
500 0.06 0.11 0.05 0.00
1,000 0.11 0.44 0.11 0.00
5,000 0.55 8.89 0.77 0.00
10,000 1.16 31.69 1.75 0.06
50,000 6.98 788.62 10.21 0.22
100,000 N/A N/A 20.60 0.44

He also compares partially sorted arrays. The result is similar.

Based on these numbers, my best bet is that Excel uses Quick Sort,
slightly faster than the VBA implementation because it is precompiled
into a binary form.
 
J

Jerry W. Lewis

For those only following the thread in microsoft.public.excel, Myrna
Larson noted in the microsoft.public.excel.worksheet.functions copy of
this thread that unlike QuickSort, Excel's sort is stable (preserves
original order where sort keys are equal).

Jerry
 
M

Michael C

Thanks for all the input. Your chart is a little hard to read, but I get
the idea. One more question - does anyone think they might be using a Radix
sort, or a variation thereof?

Thanks,
Michael C.
 
M

Michael C

Sorry, I meant to say that a Ternary QuickSort and a Radix sort are both
stable. Does anyone have any thoughts possibly one way or the other, as to
which might be the Excel internal implementation?

Thanks,
Michael C.

Michael C said:
Thanks for all the input. Your chart is a little hard to read, but I get
the idea. One more question - does anyone think they might be using a Radix
sort, or a variation thereof?

Thanks,
Michael C.
Click to expand...
 
Top