Merge Sort

Divide and Conquer:

• Split the data in half

• Sort each half recursively

• Merge the results

template <typename eType>
void mergeSort(vector<eType> list): 
    if len(list) < 2: 
        return list
    auto middle = len(list) / 2
    auto left = mergesort(list[:middle])
    auto right = mergesort(list[middle:])
    return merge(left, right)