Merge Sort in C++

Hello! Can you hear me? I've got Merge Sort for you all in C++. I thought of relying on the C++ library array and vectors. And you know what, they simplified the code and less error prone. So sit back, relax and enjoy Merge Sort.

#include<iostream>

#include<algorithm>

#include<vector>

#include<array>

using namespace std;

void merge(vector<int>& array, vector<int>& array1, vector<int>& array2) {

    array.clear();

    int i, j, k;

    for( i = 0, j = 0, k = 0; i < array1.size() && j < array2.size(); k++){

        if(array1.at(i) <= array2.at(j)){                                             // comparing the two elements of the

            array.push_back(array1.at(i));                                           two subarray and inserting the

            i++;                                                                                 smaller of the two in the main array

        }else if(array1.at(i) > array2.at(j)){

            array.push_back(array2.at(j));

            j++;

        }

        k++;

    }

    while(i < array1.size()){                                                        // inserting the remaining elements

        array.push_back(array1.at(i));                                              in the main array.

        i++;

    }

    while(j < array2.size()){                                                       // inserting the remaining elements

        array.push_back(array2.at(j));                                              in the main array

        j++;

    }

}

void merge_sort(vector<int>& array) {                                // we pass the whole array that we need to 

    if (1 < array.size()) {                                                              sort

        vector<int> array1(array.begin(), array.begin() + array.size() / 2);    // breaking it into size n/2

        merge_sort(array1);

        vector<int> array2(array.begin() + array.size() / 2, array.end());

        merge_sort(array2);

        merge(array, array1, array2);

    }

}

int main(){

    vector<int>v = {5,2,4,7,1,3,2,6};            

    merge_sort(v);                                              // calling the merge_sort function which in turn will 

    for(int &x:v)                                                    call the merge function.

        cout<<x<<" " ;

    return 0;

}

I know that merge sort takes an extra space complexity of n. But if you will try to do In place merge that will make your time complexity touch to n^2.