DEV Community

Tanuja V
Tanuja V

Posted on • Edited on

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

#mergesort #programming #beginners #algorithms

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

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)