A common task for computers is to sort data as an aid to analyzing it. There are a large number of possible sorting algorithms. We will look at (source code included) and check out time trials for the following:




   “C” Source Code for the above algorithms is on the http://www.durangobill.com/SortAlgorithms/Sort_Source_Code.html page. Permission is granted to use the source code without obligation, but if you are a student, you will be better off in the long run if you learn how the algorithms work as opposed to just copying the code. The source code program will run as is without modification if compiled with the lcc-win32 “C” compiler. http://www.cs.virginia.edu/~lcc-win32/

   A brief description of the individual algorithms is given below, but more complete documentation is included in the source code.



   Test data for the time trials was generated using a pseudo random number generator. (Included in the above source code.) This allowed each sort test to work on identical number sets. The elapsed times shown in the tables are averages for 10 different runs. While times are quoted to 1 one-thousandth of a second, true time measurement was only accurate to about 1 one-hundredth of a second. Thus the last digit should only be regarded as “a guide”.

   Time trials were run using a 3 GHz Pentium processor. No other user initiated program was running during the time trials. However, the Windows XP operating system, possible system operations, and/or who knows what might have been running in the background (e.g. system/virus updates). All of the above could have influenced the time data.




   Bubble sort is easy to code, but it is an “N squared” algorithm - and one of the least efficient of the “N squared” algorithms. The “N squared” phrase means that if you double the number of items to be sorted, the sort time will increase by a factor of four. If you multiply the number of items by 10, then the sort time will be increased by a factor of 100. Time trial tests produced the following:





   Insertion Sort is similar to the way you might sort a hand of cards. Let’s assume that you are dealt a poker or bridge hand. One way of sorting your hand is to pick up the cards one at a time, look to see what the card is, and then insert it into your hand of cards.

 While Insertion Sort is another “N Squared” algorithm, it has several advantages over “Bubble Sort”.

1) Its intrinsic efficiency makes it hard to beat for small lists. (e.g. 30 or less).

2) Insertion Sort is the basis for Shell Sort. Thus once you learn Insertion Sort, Shell Sort is just a minor “add on”.

3) Insertion Sort is very fast for arrays that are nearly sorted. It is very efficient for the final pass after Quicksort has done most of its job.

4) Modern computers have an “on board” cache memory that can be accessed much faster than ordinary random access memory. Insertion Sort does most of its “thrashing” within a small section of the array that is being sorted. This small section of the array that is being sorted is frequently in the computer’s cache memory. This further increases the efficiency of Insertion Sort. This cache memory efficiency has a significant effect on the optimal size of “MinGroup” when you are fine tuning “Quicksort”.

Of interest, compare the time trials for Insertion Sort vs. Bubble Sort






   Multiple Link List Sort is only efficient under certain conditions (see source code), but for what it does, there is probably nothing else that can match it for speed. Thus it is probably the fastest sorting algorithm (fastest sort algorithm). MLLsort is an address calculation sort. For each number that it is going to sort, it looks at the number, and calculates where it should go in the final sorted list.

   The process is very similar to the following algorithm for assembling a jig-saw puzzle. Pick up the first piece of the puzzle, compare the small picture on the puzzle piece with the picture of the entire puzzle, and place the piece in its exact location on the table where you are going to assemble the entire puzzle. Then pick up the second piece of the puzzle, and repeat the above process. Each puzzle piece is examined only once, and after you have examined each puzzle piece exactly once, the puzzle is finished.

   The quantity of elements and sort times in the table below are not mistakes. Multiple Link List Sort runs in linear time (no log(n) or log(log(n))), and it is as fast as they come.





   Quicksort is the fastest general purpose sorting algorithm. By “General Purpose”, it can handle any kind of data. It only requires minimal extra memory while MLLsort needs lots of memory.

   The bad news for Quicksort is that it is probably the most difficult to code. Also, a poorly implemented Quicksort may require “N squared” time on some data sets - which frequently includes partially sorted data. If Quicksort is coded properly, it will almost always run in “N*(Log(N))” time, and will almost always beat any other N*(Log(N)) algorithm. (e.g. It will normally beat Heapsort, Merge Sort, etc.)

   We can use our jig-saw puzzle analogy to see how Quicksort operates. First, dump all the puzzle pieces out on to a table. (Make sure you turn all the puzzle pieces right side up - although “cheating” and looking at the grain on the back side of the pieces is frequently of help.) If you are trying to solve the puzzle, you might separate (partition) the edge pieces into one group and everything else into a second group. The first pass of Quicksort performs a similar operation by separating the smaller numbers into one group and the larger numbers into a second group.

   If you are solving a jig-saw puzzle, you then might divide the “non-edge” pieces into two separate groups. (e.g. “Blue sky” in one group and everything else in the other group.) The second pass of Quicksort performs a similar operation. It takes one of the groups from “the first pass” and partitions this subgroup into groups that contain “relatively smaller values” and “relatively larger values”.

   Both the puzzle algorithm and Quicksort continue the partitioning process until the small groups (subgroups) are reduced to manageable size. If you are working on the jig-saw puzzle, you eventually assemble each of the small groups. If Quicksort is working on a list of numbers to sort, the final assembly process is performed by Insertion Sort.

   Details of the code can be seen on the Source Code page. The source code is based on original work by Robert Sedgewick (author of “Algorithms”) with a few small additions by the author.

   The variable “MinGroup” (within the code) is of interest. If all memory access into the array to be sorted has equal access time, then the optimal value for “MinGroup” is about 15 to 20. Present-day computers have an “on board” cache memory which greatly aids the final Insertion Sort, and thus alters the optimal size for “MinGroup”. The optimal size for “MinGroup” on the author’s computer is in the 60 to 70 range. Users may wish to experiment with other computers.







   If you are only going to learn one sorting algorithm, concentrate on Shell Sort. A properly coded Shell Sort is much easier to code than Quicksort, and it is nearly as fast as Quicksort.

   Shell Sort is based on Insertion Sort. In fact, if you are working on a very small group of numbers, it is exactly the same as Insertion Sort. If you are sorting a larger group, then it is just an expansion of Insertion Sort. Shell Sort breaks down large arrays into a series of small sections which it then treats as though they were “Insertion Sort”.


   For example, let's assume you are going to sort 16 elements and are using the 1, 4, 13, etc. sequence for “gap” sizes. The algorithm will first use a “Gap” size of 4. It will run 4 separate simultaneous “Insertion Sorts”. One of these will be an "Insertion Sort" on the numbers in the “A” positions. The other 3 “Insertion Sorts” will use the “B”, “C”, and “D” groups. When the “Gap = 4” process is finished, the array will be roughly sorted with most of the small value numbers concentrated near the low end of the array. Similarly, most of large value numbers will be concentrated near the high end of the array. The algorithm then continues with a “Gap” size of 1. This is essentially an ordinary “Insertion Sort”, and “Insertion Sort” is very efficient on arrays that are nearly sorted.

   While some sorting algorithms can be easily classified as executing in “N squared”, “N*Log(N)”, etc. time, Shell Sort does not fall into an easily analyzed pattern. On top of that, the sort time is a function of the “gap” sequence that is used and is somewhat a function of the cache memory that resides in a computer. Time trials used by the author included the following gap sequences:

1)  1, 3, 7, 21, 48, 112, 336, 861, 1968, 4592, 13776, 33936, 86961, 198768, 463792, 1391376, 3402672, 8382192, 21479367, 49095696, 114556624, 343669872

2)  1, 4, 13, 40, 121, 364, 1093, 3280, 9841, 29524, 88573, 265720, 797161, 2391484, 7174453, 21523360, 64570081, 193710244, 581130733, 1743392200

3)  1, 8, 23, 77, 281, 1073, 4193, 16577, 65921, 262913, 1050113, 4197377, 16783361, 67121153, 268460033, 1073790977

(See the source code for more information)

   The third sequence seems to produce the best results, but there is no final word (and probably never will be) regarding a “best sequence”.

The tables below show the results as run on the author’s computer.





Return to Durango Bill's Home Page.


Web page generated via Sea Monkey's Composer HTML editor
within  a Linux Cinnamon Mint 18 operating system.
(Goodbye Microsoft)