Sorting And Efficiency

I learned a bunch of vague concepts and abstract algorithms in middle school. That was a long dark time for any student who has no patience and self-regulation. For me, of course, algorithms are definitely not easy. However, among those tricky and  incomprehensible algorithms, sorting is the area that I spent most of my time on. I would like to share my interesting opinions about sorting algorithms here.

Sorting algorithms are useful. No one could deny that. Our computers are sorting things every single second. There are dozens of sorting algorithms scientists have analyzed and most of them have their own characteristics. These differentiate algorithms from each other. I would like to talk about the differences here.

First, i want to talk about time complexity,  the most important aspect in measuring a algorithm.

The Quick Sort,who has the fanciest name and the most mercurial time complexity, has a nlogn asymptotic complexity in best case, very decent and efficient. However, in the worst case, it seems not decent at all, a O(n^2) complexity. Quicksort is a divide and conquer algorithm which relies on a partition operation. The nlogn time complexity together with logn space usage make it one of the most popular sorting algorithms. The drawbacks of quick sort are quite obvious. Its worst-case performance is O(n^2).The most complex issue in quicksort is choosing a good pivot element , as consistently poor choices of pivots can directly result in drastically slower to a O(n^2) performance.

While there are probably a uncounted number of sorting algorithms, in practical implementations a few algorithms predominate. Like quicksort, each algorithm has its own advantages and drawbacks. Primarily heap sort, quicksort and merge sort are used for large data sets. While insertion sort is wildly used for small data sets because of its asymptotic inefficiency, decent space usage and stability.