Insertion Sort is... Crappy Mergesort?

mergeSort :: (Ord a) => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort (drop n xs)) (mergeSort (take n xs))
  where
    n = length xs `div` 2

merge :: (Ord a) => [a] -> [a] -> [a]
merge [] xs = xs
merge xs [] = xs
merge (x : xs) (y : ys)
  | x <= y = x : merge xs (y : ys)
  | otherwise = y : merge (x : xs) ys

I wrote this mergesort implementation during my algorithms lecture the other day. Initially, I was bit confused with the take n xs drop n xs part because for some reason I subconsciously thought that they worked from different ends of the list, even though they both operate from the start of the list. That is, take n xs : drop n xs is just xs. Because I was confused, I overcomplicated it to avoid including the same element in both sublists… which was exactly what ended up happening anyway.

But that’s not the interesting part. Once I realised that n was the same for both sublists, I also realised that n doesn’t necessarily need to be half the length of the list. n can be any number less than the length of the list, and this sort will still work. It’s just that n being half the length of the list is the most efficient choice, because it’s easy to split a list in two and it splits the problem into two roughly equal sub-problems, hence leading to O(log n) execution time.

That led me to think about other values of n, and n = 1 leads to a very interesting case. merge (mergeSort (drop 1 xs)) (mergeSort (take 1 xs)) is essentially merge (mergeSort (tail xs)) (mergeSort (head xs)). What this is saying is to sort the entire list except the first element, then merge the head into the sorted tail at the very end. If this sounds familiar, that’s because, at a high-level, this is exactly the same as insertion sort, except starting at the opposite end of the list.

In regular insertion sort, when you reach element k, you have already sorted all the elements 0 to k - 1 and are now going to place element k into its correct position in this sorted list. In our modified mergesort above, when we reach element k by return-ing up the call stack, all the elements k + 1 to (length xs) - 1 are already sorted; all we want to do is place the current element into its correct position in the sorted list.

Obviously, no one should ever write insertion sort this way, but I do think it’s a fun little observation that deserved to be noted down somewhere.