Post #3696139

Today I realized mergesort is the inverse of quicksort, kind of. Both algorithms are based on the idea that in order to sort an array, you 1) separate the elements into two sub-arrays, 2) recursively sort each sub-array, and 3) combine the sorted sub-arrays into one again. The difference is that quicksort does most of its work in step 1: It makes sure that all elements of sub-array 2 are bigger than all elements of sub-array 1. Then, after sorting each sub-array, step 3 is trivial: The last (biggest) element of sub-array 1 is smaller than the first (smallest) element of sub-array 2, so the two sub-arrays can be concatenated together without reördering anything. Whereas mergesort does most of its work in step 3: In step 1 it simply puts half of the elements in sub-array 1 and the other half in sub-array 2, which is trivial. Then, after sorting each sub-array, it has to merge them, which can be done in linear time, but is not free. Or in short: quicksort has a trivial merge after the recursive sort step, and mergesort has a trivial split before the recursive sort step. #sorting #algorithms