Bifalgorithm post

Merge sort recursively splits the array in half down to single elements, then merges sorted halves back together in order. That gives it a guaranteed O(n) log n runtime in the best, average and worst case, though it needs O(n) extra space since merging isn't done in place. It's a stable sort, which makes it ideal for large datasets, external sorting and cases where multi-key stability matters. Watch the recursion tree play out on the Merge Sort Lab.

Merge sort recursively splits the array in half down to single elements, then merges sorted halves back together in order. That gives it a guaranteed O(n) log…