Merge Sort is a divide-and-conquer sorting algorithm that splits an array into smaller subarrays, sorts each subarray, and then merges them back together to form a single sorted array. It is one of the most efficient sorting algorithms, particularly for large datasets.
How Merge Sort Works?
- Divide:
- The array is divided into two halves recursively until each subarray contains one element (a single-element array is already sorted).
- Conquer:
- Each of these smaller subarrays is sorted. Sorting a single-element array is trivial, so this step essentially involves merging two sorted subarrays.
- Merge:
- The sorted subarrays are merged back together in sorted order to form a larger sorted array.
Understand it with an Example:
Input Array: [38, 27, 43, 3, 9, 82, 10]
- Split into
[38, 27, 43, 3]and[9, 82, 10]. - Further split:
[38, 27],[43, 3],[9, 82],[10]. - Continue splitting until subarrays contain one element:
[38],[27],[43],[3],[9],[82],[10]. - Merge pairs back:
[27, 38],[3, 43],[9, 82],[10]. - Continue merging:
[3, 27, 38, 43],[9, 10, 82]. - Final merge:
[3, 9, 10, 27, 38, 43, 82].
Merge Sort Program in Java
package com.javacodepoint.sort;
public class MergeSort {
// Merge two sorted subarrays into a single sorted array
public static void merge(int[] array, int left, int mid, int right) {
int n1 = mid - left + 1; // Size of left subarray
int n2 = right - mid; // Size of right subarray
// Create temporary arrays
int[] leftArray = new int[n1];
int[] rightArray = new int[n2];
// Copy data to temporary arrays
for (int i = 0; i < n1; i++)
leftArray[i] = array[left + i];
for (int j = 0; j < n2; j++)
rightArray[j] = array[mid + 1 + j];
// Merge the temporary arrays back into the original array
int i = 0, j = 0, k = left;
while (i < n1 && j < n2) {
if (leftArray[i] <= rightArray[j]) {
array[k] = leftArray[i];
i++;
} else {
array[k] = rightArray[j];
j++;
}
k++;
}
// Copy remaining elements of leftArray, if any
while (i < n1) {
array[k] = leftArray[i];
i++;
k++;
}
// Copy remaining elements of rightArray, if any
while (j < n2) {
array[k] = rightArray[j];
j++;
k++;
}
}
// Sort the array using Merge Sort
public static void mergeSort(int[] array, int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// Recursively sort the left and right halves
mergeSort(array, left, mid);
mergeSort(array, mid + 1, right);
// Merge the sorted halves
merge(array, left, mid, right);
}
}
public static void main(String[] args) {
int[] numbers = { 38, 27, 43, 3, 9, 82, 10 };
System.out.println("Original Array:");
for (int num : numbers) {
System.out.print(num + " ");
}
// Sort the array
mergeSort(numbers, 0, numbers.length - 1);
System.out.println("\nSorted Array:");
for (int num : numbers) {
System.out.print(num + " ");
}
}
}
OUTPUT:
Original Array:
38 27 43 3 9 82 10
Sorted Array:
3 9 10 27 38 43 82
Time Complexity
- Best Case: O(n log n)
- Average Case: O(n log n)
- Worst Case: O(n log n)
Space Complexity
- O(n) (due to temporary arrays for merging).
Key Points about Merge Sort:
- Merge Sort divides the array into smaller subarrays until each contains one element.
- It then merges the subarrays while maintaining order.
- The recursion ensures that the algorithm always works on smaller pieces of the array, which makes it efficient.
Also Read: Selection Sort | Insertion Sort | Bubble Sort | Quick Sort