Merge Sort using divide and conquer approach (With Mistakes noted! this time!)

When writing merge sort next time, ask yourself:

✅ Did I divide properly using si, mid, ei?

✅ Did I initialize i=si and j=mid+1 in merge()?

✅ Did I correctly loop with i <= mid and j <= ei?

✅ Did I merge into a temp vector and copy back?

#include <iostream>

#include <vector>

using namespace std;

void printArray(int arr[], int n) {

    for(int i =0; i<n; i++) {

        cout << arr[i] << " ";

    }

    

    cout << endl;

}

void merge(int arr[], int si, int mid, int ei) {

    int i = si; // Major part of mistake

    int j = mid+1; // Major part of mistake

    vector<int> temp;    // Did Mistake this line 

    

    

    // Merge the two sorted halves

    while (i <= mid && j <= ei) { // Did Mistake this line 

        

        if(arr[i] < arr[j]) {

            temp.push_back(arr[i++]);

        } else {

            temp.push_back(arr[j++]);

        }

    }

    

    

    // Copy remaining elements

    while(i <= mid) {  // Did Mistake this line 

        temp.push_back(arr[i++]);

    }

    

    

    while(j <= ei) {  // Did Mistake this line 

        temp.push_back(arr[j++]);

    }

    // Copy temp back to array

    

    for(int idx = si, x=0; idx<=ei; idx++) {

        arr[idx] = temp[x++];

    }

    

}

void mergeSort(int arr[], int si, int ei) {

    if(si >= ei) {

        return;

    }

    

    int mid = si + (ei-si)/2;

    mergeSort(arr, si, mid);

    mergeSort(arr, mid+1, ei);

    merge(arr, si, mid, ei);

}

int main() {

    int arr[] = {1,4, 7,2, 10};

    int n = sizeof(arr)/sizeof(int);

    

    cout << "Original array: ";

    printArray(arr, n);

    

    

    mergeSort(arr, 0, n-1);

    

    cout << "Sorted Array: ";

    printArray(arr, n);

    return 0;

}