CP2001 Data Structures and Algorithms Sorting Page 2 of 2

Back Start

Experiments on randomly generated arrays of floating-point numbers using different sorting algorithms were compiled for different array sizes. Each sorting experiment was undertaken 100 times and the average time lapse (in ticks - 1/60th of a second) recorded.

These average-case performances are shown in the following graph [Standish]:

[Note: Be careful when using these results for your application - remember that these are average-case results using randomly generated data values].

Run-time complexities for the different sorting algorithms can be summarised as follows:

Selecting Sorting Algorithms

We have given a brief outline of the run-time performances (best-case, average-case and worst-case) of the different sorting algorithms. We have also considered their usage of memory.

Many other efficient sorting algorithms, each with advantages/disadvantages:

• Proxmap sort - computes a "proximity map" which indicates, for each key, the beginning of a sub-array in which the key will reside in the final sorted order.

  Proxmap sort runs extremely fast in the average-case -> O(N), much better than quick sort. However, proxmap can degrade significantly when the proximity contains clusters (similar to that of hashing). It also uses extra memory for storing the keys etc..

• Shell sort - repeatedly applies an insertion sort on subsequences.

  Shell sort runs in average-case O(N^{1.25}) time.

  Experiments (on random data) indicate similar performance to heap sort.

• Radix sort - a rather specialised sorting algorithm that is suited to sorting data that are characterised by several "keys". Example application is sorting integer numbers where the "keys" correspond to the 10s digit, 100s digit etc...
  Each "key" generates a "pile" of data - the piles are then combined to generate the sorted data.

  Radix sort is fast - but assumes the data can be organised into "piles".

• etc..

Moral of the Story!

Under most circumstances, it may not be crucial which sorting algorithm you choose - assuming you think about the pitfalls of each algorithm and how these might be relevant to your application.

There are two morals of the story:

1. If you absolutely need to select the best sorting algorithm, use measurement and tuning on YOUR application data to discover it.

2. Under different circumstances, different sorting algorithms will be the best.

There is no single best sorting algorithm that beats all the others all of the time.

Copyright © 1998 Olivier de Vel. All rights reserved.

Back Start