Merge Sort

1. Split array into mutually disjoint, exhaustive and adjacent subarrays, where each subarrays have at most 2 elements.
2. Sort each subarray.
3. Merging adjacent subarrays into sorted larger subarray. Use the invariant that each subarray is sorted for faster merging (see Merge Two Sorted Linked Lists).
4. Repeat step 3 until all subarrays are merged.

Implementation

class MergeSort(Sort[int]):
    def sort(self, array: list[int]) -> list[int]:
        if len(array) == 2:
            if array[0] > array[1]:
                array[0], array[1] = array[1], array[0]
            return array
        elif len(array) <= 1:
            return array
        # INVARIANT: array has >=2 elements
 
        left = self.sort(array[:2])
        right = self.sort(array[2:])
        # INVARIANT: left and right is sorted
 
        merged: list[int] = []
        while left and right:
            if left[0] < right[0]:
                merged.append(left.pop(0))
            else:
                merged.append(right.pop(0))
        # INVARIANT: left xor right is not empty
        return merged + left + right