Merge Sort
| Merge Sort |
|---|
| - Merge Sort is a sorting algorithm based on the divide and conquer technique. - Merge Sort begins by splitting the array into two halves (sub-arrays) and continues doing so recursively till a sub-array is reduced to a single element, after which the merging begins. - During the merge operation, the sub-arrays are merged in the sorted order into an auxiliary array. |
Algorithm
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.
MergeSort ( int array [ ], int low, int high )
1. If ( low < high ) then
2. mid = ( low + high ) / 2
3. Recursively split the left half : MergeSort ( array, low, mid )
4. Recursively split the right half : MergeSort ( array, mid + 1, high )
5. Merge ( array, low, mid, high )
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 additional array for merging.
Merge ( int array [ ], int low, int mid, int high )
1. While the left sub-array i.e array [ low : mid ] and the right sub-array i.e [ mid + 1 : high ] are not empty. do
2. Pick the smaller number at the front of either of the two sub-arrays and place this number in the auxiliary array.
3. If there are still numbers left in the left sub-array, then add them to the auxiliary array.
4. If there are still numbers left in the right sub-array, then add them to the auxiliary array.
5. Copy the ( sorted ) numbers from the auxiliary array back to the original array.
Example
Time complexity : 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 : O ( n ), as an auxiliary array is needed for merging the sub-arrays.
Program for sorting an array using Merge Sort
from typing import List # For annotations
# Function to merge the sorted sub-arrays into a bigger array.
def Merge (aux_array : List[int], array : List[int], low : int, mid : int, high : int):
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 : List[int], array : List[int], low : int, high : int):
if (low < high):
mid = int((low + high)/2)
MergeSort (aux_array, array, low, mid) # Recursively splits the left half of the array
MergeSort (aux_array, array, mid+1, high) # Recursively splits the right half of the array
Merge (aux_array, array, low, mid, high) # Merge the left and the 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 auxiliary 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
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]
#include<iostream>
#include<vector>
std :: vector<int> auxvec;
// Function to merge the sorted sub-arrays into a bigger array.
void Merge (std :: 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 auxiliary 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 (std :: vector<int>& vec, int low, int high) {
int mid;
if (low < high) {
mid = (low + high)/2;
MergeSort (vec, low, mid); // Recursively splits the left half of the array
MergeSort (vec, mid+1, high); // Recursively splits the right half of the array
Merge (vec, low, mid, high); // Merge the left and the right half of the array keeping it sorted.
}
}
int main(){
std :: vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};
// Allocate space for the auxiliary vector
auxvec.resize(vec.size());
MergeSort (vec, 0, vec.size()-1);
std :: cout << "Sorted numbers : ";
for (auto& it: vec)
std :: cout << it << " ";
return 0;
}
Output
Sorted numbers : 1 2 3 4 5 6 7 8
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 the left half of the array
MergeSort (array, mid + 1, high); // Recursively splits the right half of the array
Merge (array, low, mid, high); // Merge the left and the 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
Unsorted array: 7 3 5 2 4 1 8 6
Sorted array using Merge-Sort: 1 2 3 4 5 6 7 8