When we are working with a list or a dictionary, they are not usually in order. Thus, people came up with certain measures to cope with the random order so that the list becomes easier to use. Of all the famous sorting algorithms, I am going to discuss about the selection sort, quick sort, and merge sort.
Firstly, selection sort is a sorting algorithm that finds the minimum value from the remaining values and moves it to the front. As a result, swapping the values may occur very frequently in selection sort in some cases. For example, if the list is in a reversed order, more swaps will occur than when the list is in a sorted order as the program has to scan the entire list to find the smallest values that are located at the rear part of the list.
Then there is a quick sort which uses a certain value as a pivot and places the smaller values before the pivot and the bigger values after the pivot. Quick sort's efficiency depends on where the pivot is located. If the pivot is the first element of the list, then quick sort will be faster in the randomly ordered list than the sorted or reversed list. This happens because the pivot will have to change every time when there is no smaller item than the pivot.
Finally, merge sort merges the sorted lists in order. That is why merge sort is the fastest in the nearly-sorted list and the reversed list. Merge sort may be deemed similar with the quick sort as divide and conquer is the same strategy they both use. When quick sort also divides the full list into two parts and work from there, merge sort divides the full list into half so that the comparison among the two parts are optimized in terms of efficiency. Quick sort's pivot moves at one element by one while merge sort's pivot moves by half of the entire list.
However, the fastest sorting method is the built-in as the list.sort method uses different sorting algorithms based on the size of the list. Alike Timsort uses merge sort and insertion sort, built-in sort is a hybrid sorting algorithm. In other words, the efficiency of different sorting algorithms differs from every case. Usually, quick sort is the fastest in almost every cases only if it is randomly ordered. Selection sort is the slowest because it visits len method too many times if the size of the list is too big.
