Table of Contents
Merge Sort
Merge sort is a divide-and-conquer sorting algorithm that works by dividing an array into smaller subarrays, sorting them, and then merging them back together in a sorted manner. It is a stable sort, meaning that the order of equal elements is preserved, and it is a comparison-based sort, meaning that it determines the order of elements by comparing them.
Working Process
The basic idea behind merge sort is to divide the array into two halves, sort each half, and then merge the two sorted halves back together. This process is repeated recursively until the array is fully sorted.
Here is the general outline of the merge sort algorithm:
- If the array has fewer than two elements, return it (since it is already sorted).
- Divide the array into two halves.
- Sort each half by recursively applying the merge sort algorithm.
- Merge the two sorted halves back together by comparing the elements and placing them in the correct order.
Illustration
For example, consider the following unsorted array: [8, 4, 7, 3, 6, 2, 1, 5]
We can apply the merge sort algorithm as follows:
- Divide the array into two halves: [8, 4, 7, 3] and [6, 2, 1, 5]
- Sort each half by recursively applying the merge sort algorithm: [4, 8, 3, 7] and [1, 2, 5, 6]
- Merge the two sorted halves back together: [1, 2, 3, 4, 5, 6, 7, 8]
Algorithm
Here is the pseudocode for the merge sort algorithm:
def merge_sort(array):
if length of array is less than 2:
return array
else:
middle = length of array / 2
left = array[0 to middle]
right = array[middle to end]
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
return merge(left_sorted, right_sorted)
def merge(left, right):
result = []
while left and right:
if first element of left is less than or equal to first element of right:
append first element of left to result
remove first element of left
else:
append first element of right to result
remove first element of right
while left:
append first element of left to result
remove first element of left
while right:
append first element of right to result
remove first element of right
return resultTime Complexity
The time complexity of the merge sort is O(n*log(n)). This is because the algorithm divides the array into halves at each step, and the number of steps required to fully sort the array is logarithmic with respect to the size of the array.
Auxiliary Space
The auxiliary space complexity of merge sort is O(n). This is because the algorithm requires an additional array to store the merged result, which has the same size as the original array.
Applications
- Merge sort is a useful sorting algorithm for arrays that are too large to fit in memory since it can be implemented in a way that only requires storing the elements that are currently being sorted.
- It is also a good choice for sorting linked lists
Drawbacks
- One of the main drawbacks of merge sort is that it requires additional space to store the merged result, which can be a problem for large arrays that do not fit in memory.
- It is also a relatively slow sorting algorithm compared to other algorithms, such as quicksort and heapsort, which have faster average-case time complexity.
Here is the implementation of the merge sort algorithm in Python:
def merge_sort(array):
if len(array) < 2:
return array
else:
middle = len(array) // 2
left = array[:middle]
right = array[middle:]
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
return merge(left_sorted, right_sorted)
def merge(left, right):
result = []
while left and right:
if left[0] <= right[0]:
result.append(left[0])
left.pop(0)
else:
result.append(right[0])
right.pop(0)
while left:
result.append(left[0])
left.pop(0)
while right:
result.append(right[0])
right.pop(0)
return resultHere is the implementation of the merge sort algorithm in C++:
#include <iostream>
#include <vector>
using namespace std;
vector<int> merge_sort(vector<int> array) {
if (array.size() < 2) {
return array;
} else {
int middle = array.size() / 2;
vector<int> left(array.begin(), array.begin() + middle);
vector<int> right(array.begin() + middle, array.end());
left = merge_sort(left);
right = merge_sort(right);
return merge(left, right);
}
}
vector<int> merge(vector<int> left, vector<int> right) {
vector<int> result;
while (left.size() > 0 && right.size() > 0) {
if (left[0] <= right[0]) {
result.push_back(left[0]);
left.erase(left.begin());
} else {
result.push_back(right[0]);
right.erase(right.begin());
}
}
while (left.size() > 0) {
result.push_back(left[0]);
left.erase(left.begin());
}
while (right.size() > 0) {
result.push_back(right[0]);
right.erase(right.begin());
}
return result;
}
int main() {
vector<int> array = {8, 4, 7, 3, 6, 2, 1, 5};
array = merge_sort(array);
for (int i : array) {
cout << i << " ";
}
cout << endl;
return 0;
}Here is the implementation of the merge sort algorithm in Java:
import java.util.Arrays;
public class MergeSort {
public static int[] mergeSort(int[] array) {
if (array.length < 2) {
return array;
} else {
int middle = array.length / 2;
int[] left = Arrays.copyOfRange(array, 0, middle);
int[] right = Arrays.copyOfRange(array, middle, array.length);
left = mergeSort(left);
right = mergeSort(right);
return merge(left, right);
}
}
public static int[] merge(int[] left, int[] right) {
int[] result = new int[left.length + right.length];
int leftIndex = 0;
int rightIndex = 0;
int resultIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] <= right[rightIndex]) {
result[resultIndex] = left[leftIndex];
leftIndex++;
} else {
result[resultIndex] = right[rightIndex];
rightIndex++;
}
resultIndex++;
}
while (leftIndex < left.length) {
result[resultIndex] = left[leftIndex];
leftIndex++;
resultIndex++;
}
while (rightIndex < right.length) {
result[resultIndex] = right[rightIndex];
rightIndex++;
resultIndex++;
}
return result;
}
public static void main(String[] args) {
int[] array = {8, 4, 7, 3, 6, 2, 1, 5};
array = mergeSort(array);
for (int i : array) {
System.out.print(i + " ");
}
System.out.println();
}
}