Merge Sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. The merge() function is used for merging two halves. The merge(arr, l, m, r) is a key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.


public class MergeSort {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[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, 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 sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
}

Example 1: Sorting an Array of Integers

Consider an array of integers [38, 27, 43, 3, 9, 82, 10]. The Merge Sort algorithm will recursively divide this array until each sub-array contains a single element, and then merge them back together in sorted order. The result will be [3, 9, 10, 27, 38, 43, 82].

Console Output:

[3, 9, 10, 27, 38, 43, 82]

Merge Sort on Strings

Sorting an Array of Strings

Merge Sort can also be applied to strings or any other data type that supports comparison. For example, sorting an array of strings ["banana", "apple", "cherry"] will result in ["apple", "banana", "cherry"].


import java.util.Arrays;

public class MergeSortStrings {
    void merge(String arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        String L[] = new String[n1];
        String R[] = new String[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, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i].compareTo(R[j]) <= 0) {
                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 sort(String arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
    public static void main(String args[]) {
        String arr[] = {"banana", "apple", "cherry"};
        MergeSortStrings ob = new MergeSortStrings();
        ob.sort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

Console Output:

[apple, banana, cherry]

Merge Sort with Custom Comparator

Using a Custom Comparator

Sometimes, you may want to sort an array based on custom criteria. In such cases, you can implement a custom comparator. For example, sorting an array of integers in descending order can be achieved by modifying the comparison logic.


import java.util.Arrays;
import java.util.Comparator;

public class MergeSortCustomComparator {
    void merge(Integer arr[], int l, int m, int r, Comparator comp) {
        int n1 = m - l + 1;
        int n2 = r - m;
        Integer L[] = new Integer[n1];
        Integer R[] = new Integer[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, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (comp.compare(L[i], R[j]) <= 0) {
                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 sort(Integer arr[], int l, int r, Comparator comp) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m, comp);
            sort(arr, m + 1, r, comp);
            merge(arr, l, m, r, comp);
        }
    }
    public static void main(String args[]) {
        Integer arr[] = {38, 27, 43, 3, 9, 82, 10};
        MergeSortCustomComparator ob = new MergeSortCustomComparator();
        ob.sort(arr, 0, arr.length - 1, Comparator.reverseOrder());
        System.out.println(Arrays.toString(arr));
    }
}

Console Output:

[82, 43, 38, 27, 10, 9, 3]

Merge Sort on Linked List

Sorting a Linked List

Merge Sort is particularly useful for sorting linked lists. Unlike arrays, linked lists do not require extra space for merging. The merge operation can be done in-place.


class Node {
    int data;
    Node next;
    Node(int d) {
        data = d;
        next = null;
    }
}

class MergeSortLinkedList {
    Node head;

    Node sortedMerge(Node a, Node b) {
        Node result = null;
        if (a == null)
            return b;
        if (b == null)
            return a;
        if (a.data <= b.data) {
            result = a;
            result.next = sortedMerge(a.next, b);
        } else {
            result = b;
            result.next = sortedMerge(a, b.next);
        }
        return result;
    }

    Node mergeSort(Node h) {
        if (h == null || h.next == null) {
            return h;
        }
        Node middle = getMiddle(h);
        Node nextofmiddle = middle.next;
        middle.next = null;
        Node left = mergeSort(h);
        Node right = mergeSort(nextofmiddle);
        Node sortedlist = sortedMerge(left, right);
        return sortedlist;
    }

    Node getMiddle(Node h) {
        if (h == null)
            return h;
        Node slow = h, fast = h.next;
        while (fast != null) {
            fast = fast.next;
            if (fast != null) {
                slow = slow.next;
                fast = fast.next;
            }
        }
        return slow;
    }
}

Example 2: Sorting a Linked List

Given a linked list with elements 4 -> 3 -> 2 -> 1, after applying Merge Sort, the linked list will be sorted as 1 -> 2 -> 3 -> 4.

Console Output:

1 -> 2 -> 3 -> 4

Merge Sort on Large Data Sets

Handling Large Data Sets

Merge Sort is well-suited for sorting large data sets because its time complexity is O(n log n) in all cases. It is stable and works well with external sorting (e.g., sorting data stored on disk).


import java.util.Arrays;

public class MergeSortLargeDataSet {
    void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[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, 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 sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }
    public static void main(String args[]) {
        int arr[] = new int[100000]; // large data set
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int)(Math.random() * 100000);
        }
        MergeSortLargeDataSet ob = new MergeSortLargeDataSet();
        ob.sort(arr, 0, arr.length - 1);
        System.out.println("Sorted large data set.");
    }
}

Console Output:

Sorted large data set.