General Merge Sort Framework

PseudocodeMergeSort.cpp

... merge( .... ) {                         // O(n)
    .....
}

vector<int> mergeSort(vector<int> nums) {   // T(n)
    ....                                    // 1
    mergeSort(leftHalf);                    // T(n/2)
    mergeSort(rightHalf);                   // T(n/2)
    sorted = merge(leftHalft, rightHalf);   // O(n)
    return sorted;                          // O(n)
}