Merge Sort
Sorting an arrary using Merge Sort.
Merge Sort is a sorting algorithm based on the divide and conquer strategy. Merge Sort splits the array into two equal halves (sub-arrays) and continues doing so recursively. The splitting continues till a sub-array is reduced to a single element, after which merging begins. During merge operation, the sub-arrays are merged in sorted order into an auxiliary array.
This algorithm was invented by Hungarian-American mathematician John von Neumann.
The Merge Sort algorithm is as follows
Algorithm : Merge Sort
1. Split the array all the way down until each sub-array contains a single element. The splitting operation makes use of recursion and continues as recursion progresses. 2. Merge the sub-arrays into a bigger sorted sub-array using additional space. The merging operation happens during the way out of the recursion stack and requires an auxiliary array for merging.
Example of Merge Sort
Time complexity of Merge Sort : O(n log(n)). The time complexity of merging two sorted sub-arrays each of length n is 2n. Since merging happens at each level during the way out, the time complexity is O(n)*(number of levels) i.e log(n). Thus the complexity of merge sort is O(n log(n))
Space complexity of Merge Sort : O(n), as an auxiliary array is needed for mergeing the sub-arrays.
Java
Java Program to sort numbers using Merge Sort. Implemented in Java 11
class Sort {
private int aux_array[];
// Allocate space to auxiliary array which is to be used for merging the sorted elements
Sort (int sz) {
aux_array = new int[sz];
}
// Function to merge the sorted sub-arrays into a bigger array.
//void Merge (int[] aux_array, int[] array, int low, int mid, int high) {
void Merge (int[] array, int low, int mid, int high) {
int left_index = low;
int right_index = mid+1;
int aux_index = low;
/* Merge elements from array[low : mid] and array[mid+1 : high]
^ ^
| |
left_index right_index */
// Pick the smaller number between the left part and the right part
while (left_index <= mid && right_index <= high) {
if (array[left_index] <= array[right_index]) {
aux_array[aux_index++] = array[left_index++];
} else {
aux_array[aux_index++] = array[right_index++];
}
}
if (left_index <= mid) {
// There are still some unpicked numbers in the left part
for (int i = left_index; i <= mid; i++) {
aux_array[aux_index++] = array[i];
}
} else {
// There are still some unpicked numbers in the right part
for (int i = right_index; i <= high; i++) {
aux_array[aux_index++] = array[i];
}
}
// Copy numbers from the sorted auxiliary array into the original array
for (int i=low; i<=high; i++) {
array[i] = aux_array[i];
}
}
// MergeSort function splits each sub-array till only a single element is available in the sub-array
// and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
//void MergeSort (int[] aux_array, int[] array, int low, int high) {
void MergeSort (int array[], int low, int high) {
int mid;
if (low < high) {
mid = (low + high)/2;
MergeSort (array, low, mid); // Recursively splits left half of the array
MergeSort (array, mid+1, high); // Recursively splits right half of the array
Merge (array, low, mid, high); // Merge left and right half of the array keeping it sorted.
}
}
public static void main(String args[]) {
int array[] = {7, 3, 5, 2, 4, 1, 8, 6};
//int[] aux_array = new int[array.length];
System.out.print("Unsorted array: ");
for (int i=0; i<array.length; i++)
System.out.print(array[i]+" ");
System.out.println();
Sort s = new Sort(array.length);
s.MergeSort (array, 0, array.length-1);
System.out.print("Sorted array using Merge-Sort: ");
for (int i=0; i<array.length; i++)
System.out.print(array[i]+" ");
}
}
Output of Merge Sort implemented in Java 11
Unsorted array: 7 3 5 2 4 1 8 6
Sorted array using Merge-Sort: 1 2 3 4 5 6 7 8
Python
Python Program to sort numbers using Merge Sort.
#!/usr/bin/python3
# Function to merge the sorted sub-arrays into a bigger array.
def Merge (aux_array, array, low, mid, high):
left_index = low
right_index = mid+1
aux_index = low
# Merge elements from array[low : mid] and array[mid+1 : high]
# ^ ^
# | |
# left_index right_index
# Pick the smaller number between the left part and the right part
while (left_index <= mid and right_index <= high):
if (array[left_index] <= array[right_index]):
aux_array[aux_index] = array[left_index]
aux_index += 1
left_index += 1
else:
aux_array[aux_index] = array[right_index]
aux_index += 1
right_index += 1
if (left_index <= mid):
# There are still some unpicked numbers in the left part
for i in range(left_index, mid+1):
aux_array[aux_index] = array[i]
aux_index += 1
else:
# There are still some unpicked numbers in the right part
for i in range(right_index, high+1):
aux_array[aux_index] = array[i]
aux_index += 1
# Copy numbers from the sorted auxiliary array into the original array
for i in range(low, high+1):
array[i] = aux_array[i]
# MergeSort function splits each sub-array till only a single element is available in the sub-array
# and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
def MergeSort (aux_array, array, low, high):
if (low < high):
mid = int((low + high)/2)
MergeSort (aux_array, array, low, mid) # Recursively splits left half of the array
MergeSort (aux_array, array, mid+1, high) # Recursively splits right half of the array
Merge (aux_array, array, low, mid, high) # Merge left and right half of the array keeping it sorted.
def main():
array = [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
print("Unsorted array: " + str(array))
# Allocate space for the auxillary vector
aux_array = [None] * len(array)
MergeSort (aux_array, array, 0, len(array)-1)
print("Sorted array using merge sort: "+ str(array))
if __name__ == "__main__" :
main()
Output of Merge Sort implemented in Python3
Unsorted array: [7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9]
Sorted array using merge sort: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
C++ Program to sort numbers using Merge Sort.
#include<iostream>
#include<vector>
using namespace std;
vector<int> auxvec;
// Function to merge the sorted sub-arrays into a bigger array.
void Merge (vector<int>& vec, int low, int mid, int high) {
int left_index = low;
int right_index = mid+1;
int aux_index = low;
/* Merge elements from vec[low : mid] and vec[mid+1 : high]
^ ^
| |
left_index right_index */
// Pick the smaller number between the left part and the right part
while (left_index <= mid and right_index <= high) {
if (vec[left_index] <= vec[right_index]) {
auxvec[aux_index++] = vec[left_index++];
} else {
auxvec[aux_index++] = vec[right_index++];
}
}
if (left_index <= mid) {
// There are still some unpicked numbers in the left part
for (int i = left_index; i <= mid; i++) {
auxvec[aux_index++] = vec[i];
}
} else {
// There are still some unpicked numbers in the right part
for (int i = right_index; i <= high; i++) {
auxvec[aux_index++] = vec[i];
}
}
// Copy numbers from the sorted auxillary vector into the original vector
for (int i=low; i<=high; i++) {
vec[i] = auxvec[i];
}
}
// MergeSort function splits each sub-array till only a single element is available in the sub-array
// and then proceeds with the merge of the sub-arrays into a bigger auxiliary array.
void MergeSort (vector<int>& vec, int low, int high) {
int mid;
if (low < high) {
mid = (low + high)/2;
MergeSort (vec, low, mid); // Recursively splits left half of the array
MergeSort (vec, mid+1, high); // Recursively splits right half of the array
Merge (vec, low, mid, high); // Merge left and right half of the array keeping it sorted.
}
}
int main(){
vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};
// Allocate space for the auxillary vector
auxvec.resize(vec.size());
MergeSort (vec, 0, vec.size()-1);
cout << "Sorted numbers : ";
for(auto& it: vec)
cout << it << " ";
return 0;
}
Output of Merge Sort
Sorted numbers : 1 2 3 4 5 6 7 8