Merge Sort

Merge Sort is a popular sorting algorithm that follows the Divide and Conquer approach. It divides the input array into smaller subarrays, sorts them recursively, and then merges the subarrays to produce the final sorted output.

Algorithm

The Merge Sort algorithm can be summarized in three steps:

1. Divide: Divide the unsorted array into two halves, which are roughly of equal size.
2. Conquer: Recursively sort the two halves using the Merge Sort algorithm.
3. Combine: Merge the two sorted halves to produce the final sorted array.

Time Complexity

Merge Sort has a time complexity of O(n log n) in all three cases: best case, average case, and worst case. This makes it an efficient sorting algorithm for large data sets.

Space Complexity

Merge Sort has a space complexity of O(n), as it requires additional space to store the temporary subarrays during the merging process.

Example

Let's see an implementation of Merge Sort in Java:

1${code}

In this example, we have an array of integers arr and we first print the original array. Then, we apply the Merge Sort algorithm to sort the array in ascending order and print the sorted array.

Output:

1Original Array:
210 7 8 9 1 5 
3Sorted Array:
41 5 7 8 9 10 

xxxxxxxxxx

}

class MergeSort {

​

    public static void merge(int[] arr, int left, int mid, int right) {

        int n1 = mid - left + 1;

        int n2 = right - mid;

​

        int[] L = new int[n1];

        int[] R = new int[n2];

​

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

            L[i] = arr[left + i];

        }

        for (int j = 0; j < n2; j++) {

            R[j] = arr[mid + 1 + j];

        }

​

        int i = 0;

        int j = 0;

        int k = left;

​

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

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

                arr[k] = L[i];

                i++;

            } else {

                arr[k] = R[j];

                j++;

            }

            k++;