DEV Community

Tanuja V
Tanuja V

Posted on β€’ Edited on

2 1

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.

Divide & Conquer

Recursion Tree


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


Enter fullscreen mode Exit fullscreen mode

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

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more

Top comments (0)

Image of Docusign

πŸ› οΈ Bring your solution into Docusign. Reach over 1.6M customers.

Docusign is now extensible. Overcome challenges with disconnected products and inaccessible data by bringing your solutions into Docusign and publishing to 1.6M customers in the App Center.

Learn more