class Solution {
public:
    /**
     * @param A an integer array
     * @return void
     */
    void sortIntegers2(vector<int>& A) {
        // Write your code here
        vector<int>temp(A.size(),0);
        mergeSort(A,temp,0,A.size()-1);
        
    }
    
    void mergeSort(vector<int>& A,vector<int>& temp,int start,int end){
        if (start>=end) {
            return;
        }
        int mid = (start+end)/2;
        mergeSort(A,temp,start,mid);
        mergeSort(A,temp,mid+1,end);
        merge(A,temp,start,mid,end);
        
    }
    
    void merge(vector<int>& A,vector<int>& temp,int start,int mid,int end) {
       int i = start;
       int j = mid+1;
       int k = start;
       while(i<=mid && j<=end) {
           if(A[i]>A[j]) {
               temp[k] = A[j++];
           } else {
               temp[k] = A[i++];
           }
           k++;
       }
       while(i<=mid){
           temp[k++] = A[i++];
       }
       while(j<=end){
           temp[k++] = A[j++];
       }
       for(int p = start;p<=end;p++){
           A[p] = temp[p];
       }
       
    }
    
};