Merge Sort

Merge Sort is a popular sorting algorithm that follows the divide and conquer approach. It divides the input array into two halves, sorts each half separately, and then merges them back together. Merge Sort is a stable, comparison-based algorithm that has an average and worst-case time complexity of O(n log n).

The algorithm is implemented recursively. To sort an array, it first divides it into two halves, and then recursively sorts each half. Finally, it merges the two sorted halves back together to produce the final sorted array. The merge function is the key part of the algorithm that merges the two sorted halves.

Here is an example of Merge Sort code in C++:

void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

    int L[n1], R[n2];

    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    int i = 0;
    int j = 0;
    int k = l;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        }
        else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        int m = l + (r - l) / 2;

        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        merge(arr, l, m, r);
    }
}

The merge function takes three arguments: the input array, the left index, the middle index, and the right index. It creates two temporary arrays to hold the left and right halves of the array. Then it compares the elements of these two halves and merges them back into the input array in a sorted order.

The mergeSort function takes three arguments: the input array, the left index, and the right index. It first checks if the left index is less than the right index. If yes, it calculates the middle index and recursively calls mergeSort on the left and right halves of the array. Finally, it calls the merge function to merge the two sorted halves.

If you are struggling with implementing Merge Sort in your project or Tutoring, our Tutoring Lounge tutors can provide you with the necessary guidance and help you understand the algorithm better. Our tutors have experience in teaching data structures and algorithms, and can help you gain a deeper understanding of the topic.