mergeSort2 is an implementation of merge sort that uses O(n) extra space (copies the array exactly once) instead of O(nlog(n))

mergesort.cpp

#include <iostream>
#include <vector>
#include <random>

using namespace std;

/* Returns whether a list is sorted */
bool isSorted(vector<int> & list);

/* Sorts a list using the standard merge sort algorithm everyone learns in school (requires O(nlog(n)) space) */
void mergeSort(vector<int> & list);

/* Sorts a list using an optimized version of the merge sort algorithm (makes only one copy of the list) */
void mergeSort2(vector<int> & list);

void mergeSort_sort(vector<int>::iterator sourceBegin,
                    vector<int>::iterator sourceEnd,
                    vector<int>::iterator destinationBegin,
                    vector<int>::iterator destinationEnd);

/* Merges the sorted elements from source1 and source2 into the destination */
void mergeSort_merge(vector<int> & source1, vector<int> & source2, vector<int> & destination);

/* Merges the sorted elements from source1 (from source1Begin to source1End)
 * and source2 (from source2Begin to source2End) into the destination (destinationBegin - destinationEnd)
 */
void mergeSort_merge(vector<int>::iterator source1Begin,
                     vector<int>::iterator source1End,
                     vector<int>::iterator source2Begin,
                     vector<int>::iterator source2End,
                     vector<int>::iterator destinationBegin,
                     vector<int>::iterator destinationEnd);

/* Copies the source (from sourcePos to sourceLimit) into
 * the destination (from destinationPos to destinationLimit)
 */
void copy(vector<int>::iterator sourcePos,
          vector<int>::iterator sourceLimit,
          vector<int>::iterator destinationPos,
          vector<int>::iterator destinationLimit);

int main() {
    
    /* System's random device */
    random_device device;

    /* One of C++11's good random number generators, seeded with the device */
    mt19937 rng(device());

    /* The random number distribution */
    uniform_int_distribution<int> distribution(0, 0x7FFFFFFF);

    vector<int> list(10000);

    for (auto & num : list) {
        /* Generates a random number within the distribution using the rng */
        num = distribution(rng);
        cout << num << endl;
    }

    cout << endl;

    //mergeSort(list);
    mergeSort2(list);

    for (auto num : list) {
        cout << num << endl;
    }

    cout << endl;

    if (isSorted(list)) {
        cout << "Sorted\n";
    } else {
        cout << "Not Sorted\n";
    }

    return 0;
}

bool isSorted(vector<int> & list) {
    
    if (list.size() < 2) {
        return true;
    }

    for (auto it = list.begin() + 1; it != list.end(); ++it) {
        if(*(it - 1) > *it) {
            return false;
        }
    }

    return true;
}

void mergeSort(vector<int> & list) {
    if (list.size() < 2) {
        return;
    }

    vector<int> list1(list.begin(), list.begin() + list.size() / 2);
    vector<int> list2(list.begin() + list.size() / 2, list.end());

    mergeSort(list1);
    mergeSort(list2);
    mergeSort_merge(list1, list2, list);
}

void mergeSort2(vector<int> & list) {
    if (list.size() < 2) {
        return;
    }

    vector<int> source = list;

    mergeSort_sort(source.begin(), source.end(), list.begin(), list.end());
}

void mergeSort_sort(vector<int>::iterator sourceBegin,
                    vector<int>::iterator sourceEnd,
                    vector<int>::iterator destinationBegin,
                    vector<int>::iterator destinationEnd) {

    auto size = distance(sourceBegin, sourceEnd);
    if (size < 2) {
        return;
    }

    auto sourceMiddle = sourceBegin + size / 2;
    auto destinationMiddle = destinationBegin + size / 2;

    auto source1Begin = destinationBegin;
    auto source1End = destinationMiddle;
    auto source2Begin = destinationMiddle;
    auto source2End = destinationEnd;

    auto destination1Begin = sourceBegin;
    auto destination1End = sourceMiddle;
    auto destination2Begin = sourceMiddle;
    auto destination2End = sourceEnd;

    mergeSort_sort(source1Begin, source1End, destination1Begin, destination1End);
    mergeSort_sort(source2Begin, source2End, destination2Begin, destination2End);

    mergeSort_merge(destination1Begin, destination1End,
                    destination2Begin, destination2End,
                    destinationBegin, destinationEnd);

}

void mergeSort_merge(vector<int> & source1, vector<int> & source2, vector<int> & destination) {
    mergeSort_merge(source1.begin(), source1.end(),
                    source2.begin(), source2.end(),
                    destination.begin(), destination.end());
}

void mergeSort_merge(vector<int>::iterator source1Begin,
                     vector<int>::iterator source1End,
                     vector<int>::iterator source2Begin,
                     vector<int>::iterator source2End,
                     vector<int>::iterator destinationBegin,
                     vector<int>::iterator destinationEnd) {

    auto it1 = source1Begin;
    auto it2 = source2Begin;

    for (auto spot = destinationBegin; spot != destinationEnd; ++spot) {
        if (it1 == source1End) {
            copy(it2, source2End, spot, destinationEnd);
            break;
        } else if (it2 == source2End) {
            copy(it1, source1End, spot, destinationEnd);
            break;
        } else if (*it1 < *it2) {
            *spot = *it1;
            ++it1;    
        } else {
            *spot = *it2;
            ++it2;
        }
    }
}

void copy(vector<int>::iterator sourcePos,
          vector<int>::iterator sourceLimit,
          vector<int>::iterator destinationPos,
          vector<int>::iterator destinationLimit) {

          while(sourcePos != sourceLimit && destinationPos != destinationLimit) {
              *destinationPos = *sourcePos;
              ++sourcePos;
              ++destinationPos;
          }
}