Algorithm Sort

vector<int> merge_sort(vector<int>&arr) {
    if (arr.size() <= 1) {
        return arr;
    }
    
    int middle = (0 + arr.size()) / 2;
    vector<int> partition1 = vector(arr.begin(), arr.begin() + middle);
    vector<int> partition2 = vector(arr.begin() + middle, arr.end());
    
    //sort each part recursively
    partition1 = merge_sort(partition1);
    partition2 = merge_sort(partition2);
    
    //merge all partitions together
    vector<int>output;
    int i = 0, j = 0;
    while (true) {
        int a = partition1[i];
        int b = partition2[j];
        if (a < b) {
            i++;
            output.push_back(a);
        } else {
            j++;
            output.push_back(b);
        }
        if (i == partition1.size()) {
            for (; j < partition2.size(); j++) {
                output.push_back(partition2[j]);
            }
            break;
        }
        if (j == partition2.size()) {
            for (; i < partition1.size(); i++) {
                output.push_back(partition1[i]);
            }
            break;
        }
    }
}