Sorts Sorts Sorts

Selection sort is probably one of the most natural algorithms for a programmer to implement, and may come to mind even before insertion sort, as it is conceptually extremely simple. The algorithm consists of taking the smallest item in the original list and adding it to the empty sorted list. This could be done in place or using two different lists. It can also be implemented to be stable, keeping elements of equal value in the same order. However, the simplicity of this algorithm means that it needs to scan the whole list n times, for each time it adds an element to the sorted array it needs to find the next least element, preforming (i-1) comparisons, leading to (n-1)+(n-2)+(n-3)… comparisons, or (n-1)(n-2)/2 comparisons, or a big O of n^2.

While selection sort can be implemented on small lists (really small), the inefficiency of the algorithm prevents it from having much use in practical applications. The two staple sorts which are easy to implement and provide adequate performance are quick sort and merge sort.

Quick sort is the next fastest of the three, according to sticky bigO performance. It runs in an average n log n time, and it is implemented also quite simply. To quick sort, one picks an element of the list to act as a pivot. The list is then partitioned into a part that contains all elements smaller than the pivot, and a part that contains all elements larger than the pivot. The two partitions are then themselves quick sorted, until all partitions contain one or 0 elements, which are already sorted. On average the list is split log n times, if the list is split approximately in half by the pivot. It then takes n comparisons to do the actual split, as we need to compare every element to the pivot. So we do n comparisons log n times on average, leading to a performance of nlogn. However, in the worst case the list is nearly sorted, so the pivot ends up splitting the list into an empty list and a list of n-1 elements. Then we do n comparisons to split the list, and end up making n splits, leading to a worst case performance of n^2, similar to selection sort. However, the probability of encountering an already sorted list is relatively small, so in practice Quick Sort lives up to its name, and it was included as the standard sort for the C and C++ libraries until the more complicated hybrid sorts timsort and introsort became more common.

The third sorting algorithm is MergeSort, an algorithm which is a strictly n log n sort. Mergesort works by recursively splitting the list in half until you are left with lists of length 1, and then merging the lists so that the elements within the list are sorted, until you are left with one sorted list. The splitting once again takes log n steps, and then the merge takes n comparisons for each split up list, leading to a NlogN efficiency. As the lists are always split in half, the process is guaranteed to only make order of logN splits.