## DEV Community

Tanuja V

Posted on • Updated on

# 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.

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 🥳👏