Merge Sort in Java (With Intuition + Dry run + Code)

Merge Sort is a popular sorting algorithm that follows the Divide and Conquer approach.

Here's a high-level explanation of how Merge Sort works:

Divide: The unsorted list is divided into two halves until each sublist contains only one element. This process continues recursively until we can't divide the sublists anymore.

Conquer: Once we reach the base case (sublists of size one), we start merging the sublists in a sorted order. This is done by comparing the elements of the two sublists and placing them in the correct order into a new list.

Combine/Merge: As we merge the sublists, we create larger sorted sublists until we have a single sorted list that contains all the elements of the original unsorted list.

 java
public class MergeSort {
    public static void main(String[] args) {
        int arr[] = {1, 7, 6, 8, 0, 9, 4, 5};
        int n = arr.length;

        mergeSort(arr, 0, n-1);

        for(int i=0; i<n; i++){
            System.out.print(arr[i]+" ");
        }
    }

  private static void mergeSort(int arr[], int left, int right){
        if(left>=right)
        return;

        int mid = left+(right-left)/2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid+1, right);

        merge(arr, left, mid, right);
    }

   private static void merge(int arr[], int left, int mid, int right){
        int n1 = mid-left+1;
        int n2 = right-mid;

        int leftArr[] = new int[n1];
        int rightArr[] = new int[n2];

        for(int i=0; i<n1; i++){
            leftArr[i] = arr[left+i];
        }

        for(int i=0; i<n2; i++){
            rightArr[i] = arr[mid+1+i];
        }

        int i = 0, j = 0, k = left;

        while(i<n1 && j<n2){
            if(leftArr[i]<=rightArr[j])
            arr[k++] = leftArr[i++];

            else
            arr[k++] = rightArr[j++];
        }

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

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

Time Complexity:

Best Case: O(NlogN)
Worst Case: O(NlogN)

Space Complexity:

O(N)

Wrapping Up:

Now, congrats, you've learned merge sort 🥳👏
Thanks for reading :)
Feel free to comment and like the post if you found it helpful
Follow for more 🤝 && Happy Coding 🚀

If you enjoy my content, support me by following me on my other socials:
https://linktr.ee/tanujav7