Merge sort is a popular sorting algorithm that follows the divide-and-conquer paradigm. It divides the input array into smaller subarrays, sorts them recursively, and then merges the sorted subarrays to produce a final sorted array.
Various Sorting Algorithm
- Bubble sort
- Modified Bubble Sort
- Selection sort
- Insertion sort
- Quick sort
- Merge sort
- Heap sort
Merge Sort
0 1 2 3 4 5 6 7 8 9 10 11 12
75 29 83 42 16 90 56 34 20 71 88 92 7
………………………………
………………………………
29 75 42 83 16 90 56 20 34 71 88 92 7
29 42 75 83 16 56 90 20 34 71 7 88 92
16 29 42 56 75 83 90 7 20 34 71 88 92
7 16 20 29 34 42 56 71 75 83 88 90 92
Here is the step-by-step process of the merge sort algorithm:
- If the array has more than one element, split the array into two halves.
- Recursively call merge sort on the two halves.
- Merge the two sorted halves back into a single sorted array.
Algorithm
The merge sort algorithm is based on the divide-and-conquer paradigm and operates as follows:
- Divide: Divide the unsorted array into two halves.
- Conquer: Recursively sort the two halves.
- Combine: Merge the two sorted halves to produce a single sorted array.
mergeSort(arr[], l, r)
If r > l
1. Find the middle point to divide the
array into two halves:
middle m = l+ (r-l)/2
2. Call mergeSort for the first half:
Call mergeSort(arr, l, m)
3. Call mergeSort for the second half:
Call mergeSort(arr, m+1, r)
4. Merge the two halves sorted in step
2 and 3:
Call merge(arr, l, m, r)
merge(arr[], l, m, r)
1. Find sizes of two subarrays to be merged:
n1 = m - l + 1
n2 = r - m
2. Create temporary arrays L[] and R[]:
L[] = arr[l..m]
R[] = arr[m+1..r]
3. Merge the temporary arrays back into arr
[l..r]:
Initialize indices i and j
for the two subarrays
Initialize index k for the merged array
While i < n1 and j < n2
If L[i] <= R[j]
arr[k] = L[i]
i++
Else
arr[k] = R[j]
j++
k++
Copy the remaining elements of L[],
if there are any
Copy the remaining elements of R[],
if there are any
Working Of Insertion Sort Algorithm
Certainly! Let’s go through the working of the Merge Sort algorithm step by step with an example and corresponding diagrams. Consider the following unsorted array:
38,27,43,3,9,82,10
- Divide: Divide the array into smaller subarrays recursively until each subarray has only one element.38,27,43,3,9,82,10is divided into 38,27,43 and 3,9,82,10
Conquer: Sort the divided subarrays.
38,27,43 becomes 27,38,43
3,9,82,10 becomes 3,9,10,82
Combine: Merge the sorted subarrays to produce the final sorted array.
Merge 27,38,43 and 3,9,10,82 to get the final sorted array:
3,9,10,27,38,43,82
The following diagram illustrates the step-by-step process of the Merge Sort algorithm:
Initial Array:
[38, 27, 43, 3, 9, 82, 10]
Divide:
[38, 27, 43, 3, 9, 82, 10]
/ \
[38, 27, 43] [3, 9, 82, 10]
Conquer:
[27, 38, 43] [3, 9, 10, 82]
Combine:
[3, 9, 10, 27, 38, 43, 82]
Merge Sort Complexity
The Merge Sort algorithm has the following time and space complexities:
| Case | Time Complexity |
|---|---|
| Best Case | O(n*logn) |
| Average Case | O(n*logn) |
| Worst Case | O(n*logn) |
- Best Case Complexity – It occurs when there is no sorting required, i.e. the array is already sorted. The best-case time complexity of merge sort is O(n*logn).
- Average Case Complexity – It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of merge sort is O(n*logn).
- Worst Case Complexity – It occurs when the array elements are required to be sorted in reverse order. That means suppose you have to sort the array elements in ascending order, but its elements are in descending order. The worst-case time complexity of merge sort is O(n*logn).
Implementation Of Merge Sort
Certainly! Below is a simple implementation of the Merge Sort algorithm in Java:
import java.util.Arrays;
public class MergeSort {
public void mergeSort(int[] arr,
int l, int r)
{
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public void merge(int[] arr, int l
, int m, int r)
{
int n1 = m - l + 1;
int n2 = r - m;
int[] left = new int[n1];
int[] right = new int[n2];
for (int i = 0; i < n1; ++i) {
left[i] = arr[l + i];
}
for (int j = 0; j < n2; ++j) {
right[j] = arr[m + 1 + j];
}
int i = 0, j = 0, k = l;
while (i < n1 && j < n2) {
if (left[i] <= right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = left[i];
i++;
k++;
}
while (j < n2) {
arr[k] = right[j];
j++;
k++;
}
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
MergeSort ob = new MergeSort();
System.out.println("Original array: "
+ Arrays.toString(arr));
ob.mergeSort(arr, 0, arr.length - 1);
System.out.println("Sorted array: "
+ Arrays.toString(arr));
}
}
