Merge Sort
Time Complexity
| Best | Average | Worst |
|---|---|---|
| Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
Space Complexity
| Worst |
|---|
| O(n) |
Overview
Merge Sort is one of the most popular divide-and-conquer algorithms out there and it perfectly illustrates the division part. It breaks down the input list into smaller sub-lists, sorts them individually, and then merges them back together in a sorted order. So let's dive into the mechanics of the algorithm step-by-step using the animation input list - [3, 1, 5, 2, 8, 4, 6, 7].
- Divide the list into sub-lists.
Initially, the input list is divided into individual elements as sub-lists:
[3] [1] [5] [2] [8] [4] [6] [7]
- Merge the adjacent sub-lists by sorting them as they are merged.
The merging process involves comparing the first elements of each sub-list and placing them in the correct order. Continue this process until all sub-lists are merged.
Merge [3] and [1]: [1, 3]
Merge [5] and [2]: [2, 5]
Merge [8] and [4]: [4, 8]
Merge [6] and [7]: [6, 7]
- Now, merge the previously merged sub-lists to obtain a fully sorted list.
Merge [1, 3] and [2, 5]: [1, 2, 3, 5]
Merge [4, 8] and [6, 7]: [4, 6, 7, 8]
- Finally, merge the last two sorted sub-lists.
Merge [1, 2, 3, 5] and [4, 6, 7, 8]: [1, 2, 3, 4, 5, 6, 7, 8]
- We finally have the sorted list.
We have the sorted list: [1, 2, 3, 4, 5, 6, 7, 8].
In conclusion, Merge Sort is a great algorithm for large lists due to its time complexity of O(n log n) - for best, average, and worst cases. Also, it's a stable algorithm, which means that it maintains the order of same elements next to each other. It's still important to know that additional memory consumption is required to store the sublists but generally, this shouldn't be much of a problem so merge sort is often a good choice for various sets of data. And, it's a great algorithm to practice and learn from!
Code
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_sublist = arr[:mid]
right_sublist = arr[mid:]
left_sublist = merge_sort(left_sublist)
right_sublist = merge_sort(right_sublist)
merge(arr, left_sublist, right_sublist)
return arr
def merge(arr, left, right):
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
input_list = [3, 1, 5, 2, 8, 4, 6, 7]
sorted_list = merge_sort(input_list)
print(sorted_list)
function mergeSort(arr) {
if (arr.length <= 1) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const leftSublist = arr.slice(0, mid);
const rightSublist = arr.slice(mid);
mergeSort(leftSublist);
mergeSort(rightSublist);
merge(arr, leftSublist, rightSublist);
return arr;
}
function merge(arr, left, right) {
let i = j = k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < left.length) {
arr[k] = left[i];
i++;
k++;
}
while (j < right.length) {
arr[k] = right[j];
j++;
k++;
}
}
const inputArray = [3, 1, 5, 2, 8, 4, 6, 7];
const sortedArray = mergeSort(inputArray);
console.log(sortedArray);
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
int[] arr = {3, 1, 5, 2, 8, 4, 6, 7};
mergeSort(arr);
System.out.println(Arrays.toString(arr));
}
public static void mergeSort(int[] arr) {
if (arr.length <= 1) {
return;
}
int mid = arr.length / 2;
int[] leftSubarray = Arrays.copyOfRange(arr, 0, mid);
int[] rightSubarray = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(leftSubarray);
mergeSort(rightSubarray);
merge(arr, leftSubarray, rightSubarray);
}
public static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
arr[k] = left[i];
i++;
} else {
arr[k] = right[j];
j++;
}
k++;
}
while (i < left.length) {
arr[k] = left[i];
i++;
k++;
}
while (j < right.length) {
arr[k] = right[j];
j++;
k++;
}
}
}
#include <stdio.h>
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
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);
}
}
int main() {
int arr[] = {3, 1, 5, 2, 8, 4, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, n - 1);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
return 0;
}
function mergeSort(array &$arr) {
$len = count($arr);
if ($len <= 1) {
return;
}
$mid = (int) ($len / 2);
$leftArray = array_slice($arr, 0, $mid);
$rightArray = array_slice($arr, $mid);
mergeSort($leftArray);
mergeSort($rightArray);
merge($arr, $leftArray, $rightArray);
}
function merge(array &$arr, array $left, array $right) {
$i = $j = $k = 0;
$leftSize = count($left);
$rightSize = count($right);
while ($i < $leftSize && $j < $rightSize) {
if ($left[$i] < $right[$j]) {
$arr[$k] = $left[$i];
$i++;
} else {
$arr[$k] = $right[$j];
$j++;
}
$k++;
}
while ($i < $leftSize) {
$arr[$k] = $left[$i];
$i++;
$k++;
}
while ($j < $rightSize) {
$arr[$k] = $right[$j];
$j++;
$k++;
}
}
$inputArray = [3, 1, 5, 2, 8, 4, 6, 7];
mergeSort($inputArray);
print_r($inputArray);