Sort a mess of socks with the most efficient algorithmic approach - Merge Sort!
Take your socks and divide them into two piles, one for each type.
Sort each pile in a sorted order, using a stable algorithm.
Take the sorted piles and merge them into a single, sorted list.