Merge Sort In Java

Merge sort is a popular sorting algorithm that follows the divide-and-conquer approach. It efficiently sorts a list or an array by recursively dividing it into smaller sublists, sorting them, and then merging them back together to produce the final sorted result. The basic steps of the merge sort algorithm can be explained as follows:

1. Divide: The algorithm starts by dividing the original list into two halves repeatedly until each sublist contains only one element. This is done recursively until the base case is reached.

2. Conquer: Once the sublists have been divided into individual elements, they are considered sorted by default. At this stage, the algorithm begins merging the sublists in sorted order. The merging process compares the elements from the sublists and merges them into a new sorted sublist.

3. Merge: The merge operation compares the elements from two sorted sublists and places them in the correct order in a new temporary sublist. The process continues until all the elements from both sublists are merged into a single sorted sublist.

4. Repeat: Steps 2 and 3 are repeated recursively for each pair of sublists until there is only one sorted sublist remaining, which represents the fully sorted list.

To illustrate the merge sort algorithm, let's consider an example where we want to sort the following list of numbers in ascending order: [7, 2, 5, 3, 1, 6, 4].

1. Divide: The original list is divided into two halves: [7, 2, 5] and [3, 1, 6, 4].

   • The first half is further divided into [7], [2, 5].

   • The second half is further divided into [3, 1] and [6, 4].

   • The recursive division continues until each sublist contains only one element.

2. Conquer and Merge: Starting from the bottom, the algorithm merges the sublists in sorted order:

   • [7] and [2, 5] are merged into [2, 5, 7].

   • [3] and [1] are merged into [1, 3].

   • [6] and [4] are merged into [4, 6].

   • The two resulting sublists [1, 3] and [4, 6] are merged into [1, 3, 4, 6].

   • Finally, [2, 5, 7] and [1, 3, 4, 6] are merged into the fully sorted list [1, 2, 3, 4, 5, 6, 7].

3. Repeat: The process is repeated recursively for each pair of sublists until there is only one sorted sublist remaining, which represents the fully sorted list.

Merge sort has a time complexity of O(n log n), where n represents the number of elements in the list. It is considered a highly efficient sorting algorithm and is often used for large datasets due to its stable performance.

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int arr[] = {4,3,5,2,5,3,2,5,5,4,2,2,4,5,1,7,9,7,5,1};
        mergeSort(arr);
        printArray(arr);
    }
    private static void mergeSort(int[] arr) {
        divide(arr,0,arr.length-1);    
    }
    private static void divide(int arr[], int si, int ei)
    {
        if (si < ei) { 
            // Find the middle point
            int mid = si + (ei - si) / 2; 
            // divide first and second halves
            divide(arr, si, mid);
            divide(arr, mid + 1, ei); 
            // sort
            sort(arr, si, mid, ei);
        }
    }
    private static void sort(int arr[], int si, int m, int ei)
    {
        // Find sizes of two subarrays to be merged
        int n1 = m - si + 1;
        int n2 = ei - m; 
        // Create temp arrays
        int L[] = new int[n1];
        int R[] = new int[n2]; 
        // Copy data to temp arrays
        for (int i = 0; i < n1; ++i)
            L[i] = arr[si + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];

        // Merge the temp arrays 
        // Initial indices of first and second subarrays
        int i = 0, j = 0;

        // Initial index of merged subarray array
        int k = si;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            }
            else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[] if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        } 
        // Copy remaining elements of R[] if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void printArray(int[] outputArr) {
        System.out.println(Arrays.toString(outputArr));        
    }
}

OUTPUT

Sort.mergeSort() : nlogn

[1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, 7, 7, 9]