Merge Sort

Merge Sort is a popular sorting algorithm that follows the divide-and-conquer approach. It divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce the final sorted output.

The algorithm consists of two main steps: the splitting step and the merging step.

Splitting Step

In the splitting step, the algorithm repeatedly divides the input array into two halves until the size of each subarray becomes 1 or 0. This can be done by finding the midpoint of the array and recursively splitting the array into two parts: the left subarray and the right subarray.

Merging Step

In the merging step, the algorithm merges the two sorted subarrays into a single sorted array. It compares the elements from the two subarrays and inserts them into the resulting array in sorted order. This process is repeated until all the elements from both subarrays have been merged.

Here's an example implementation of the Merge Sort algorithm in Java:

{{code}}

The merge function merges two sorted subarrays: arr[l..m] and arr[m+1..r]. It first copies the elements from the subarrays to temporary arrays L and R, and then merges the elements back into the original array arr in sorted order.

The mergeSort function is the main driver function that recursively sorts the input array. It calls itself to sort the left and right halves of the array, and then merges the sorted halves using the merge function.

Try running the example code to see Merge Sort in action. It sorts the array [5, 2, 8, 12, 1, 7] and prints the sorted array [1, 2, 5, 7, 8, 12].

xxxxxxxxxx

}

// Merge two subarrays of arr[]

// First subarray is arr[l..m]

// Second subarray is arr[m+1..r]

void merge(int arr[], int l, int m, int r) {

    // Calculate sizes of two subarrays

    int n1 = m - l + 1;

    int n2 = r - m;

​

    // Create temporary arrays

    int L[] = new int [n1];

    int R[] = new int [n2];

​

    // Copy data to temporary arrays

    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];

​

    // Merge the temporary arrays

​

    // Initial indexes of first and second subarrays

    int i = 0, j = 0;

​

    // Initial index of merged subarray array

    int k = l;

    while (i < n1 && j < n2) {

        if (L[i] <= R[j]) {

            arr[k] = L[i];

            i++;