MergeSort

 
void Merge(int* arr, int start, int end, int* temp) {
    
    int first = start;
    int mid = (start + end) / 2;
    int second = mid + 1;
 
    for (int i = start; i <= end; i++) {
        if(first <= mid && (second > end || arr[first] < arr[second])) {
            temp[i] = first;
            first++;
        }
        else {
            temp[i] = second;
            second++;
        }
    }
    
    for (int i = start; i <= end; i++)
        arr[i] = temp[i];
}
void MergeSort(int* arr, int start, int end, int* temp) {
    if (start >= end) return;
 
    int mid = (start + end) / 2;
 
    MergeSort(arr, start, mid, temp);
    MergeSort(arr, mid + 1, end, temp);
 
    Merge(arr, start, end, temp);
 
    
}