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

Top comments (0)

Heroku

Build apps, not infrastructure.

Dealing with servers, hardware, and infrastructure can take up your valuable time. Discover the benefits of Heroku, the PaaS of choice for developers since 2007.

Visit Site