Sorting and Practicality

Sorting, and the practicality of such algorithms is a significant area of study in computer science. How do we sort large amounts of data in a reasonable amount of time? Attempts to answer this question have resulted in numerous algorithms being created, and perhaps the most popular 3 that are taught in lower level courses are Selection Sort, Quicksort and Merge Sort

Selection sort is the simplest of the trio. It is an in-place sort and takes the minimum element of the unsorted list, and adds it in place in the sorted list. It is simple, yet slow for larger lists, having O(n²) time complexity. This may not seem slow, however when working with thousands of items this can take minutes to sort the list, as compared to seconds with quicksort or even merge sort. I personally havent found much use for this particular algorithm as it still performs worse than insertion sort when used on its optimal input (smaller lists).



Quicksort is the next simplest. It works recursively, taking whats known as a pivot element, and sorting items to the left and right of it depending on if they are less than or greater than the pivot. Its' average case complexity is O(nlogn) however there are cases where it can perform as O(n²). Overall I find quicksort to be the simplest, and the most useful of the sorting algorithms taught, however it too is outperformed by other algorithms.



Merge Sort is the final one we were fully taught. Like Quicksort, it is recursive and is a divide and conquer algorithm. It works by dividing the list continually into halves until the list is one element long, at which point it is sorted by default and is then merged together with the other halves. Like Quicksort, mergesort is also O(nlogn).



I feel it is worth noting that there is no single best sorting algorithm. All sorts are data dependent and context dependent. For small enough lists, selection and insertion sort can outperform the recursive algorithms like quicksort and mergesort. Also worth noting, time efficiency does not mean space efficiency. In situations where memory space is limited, some algorithms which may be faster in an academic environment lose their usefulness.