Sorting data is a common need in many applications. If you have thought about writing your own sorting routine, you likely came up with a scheme that picked the first data item, and then compared it to each of the other elements to find a smaller value (if sorting into ascending order) or a larger value (if sorting into descending order). Finding a match, you switch the two values in your list of data.

Gradually, as you scan the list, the smallest (or largest) value bubbles up to the front of the list. Once the whole list is scanned, you have found the smallest (or largest) value and switched it to the beginning.

Then you would start with the next data value and compare it to the remaining data values. And so on.

Great idea if you came up with this – seriously! In computer science algorithms, this is known as the “bubble sort”. It works fine – but it has one problem – as the number of items to be sorted grows, the time it takes to do the sort grows even faster.

In fact, we say that a bubble sort runs in a time proportional to n^2 (n squared). If there are 10 items to sort, this will take 10^2 or 100 time units to sort.

If there are 30 items to sort, this will take 30^2 or 900 time units to sort. Just going from 10 items to 30 items adds 800 time units to our sorting time! Ouch!

As you can see, the bubble sort is simple but it can take a long time to run!

Computer scientists have invented other ways to sort data. One of the best known has the descriptive name “QuickSort”. In many cases, it’s sorting time is on the order of n ln n (that is n times the natural logarithm of n).

If we compare that to the Bubble Sort for n=10, we get 23 time units and for n=30, we get 103 time units. As you can see, QuickSort is much faster than the Bubble Sort.

Continue reading →