Bringing Order to the World

What better way to establish world order, than to use a really good sorting algorithm.
Among my favorite ways to sort is the classic merge sort. It has many things to recommend it. First of all, one of the family of O(n log n) sorts. However, it is more stable than the quick sort which only averages O(n log n) but can exhibit O(n²) behavior in some depending on how the data is organized. It is also fairly easy to understand.

The merge sort uses the principle of divide and conquer. It first divides the list into two equal sublists, sorts each sublist and then merges them together putting each element in its proper order. How does it sort each sublist? Easy, you use the merge sort on each one, splitting them into two sublists and sorting each sublist the same way. Basically, you divide each list into smaller and smaller sublists until there are only 2 elements in the list, at which point you compare the two and put them in order. Obviously, this algorithm lends itself to being implemented recursively.

There is a drawback to this sort. It takes up O(n) extra space in memory due to the fact that when you do the merge, you copy the elements into a new list in the proper order and then copy the new list back in place in the original list. The can reduced to O(log n) extra memory if you implement the sort using a linked list due to the fact that you don't need to copy since you can just change the link references on each element.

Want to learn more? Then check out my reference: http://www.sorting-algorithms.com/