# Merge Sort Algorithm

Merge Sort is an array sorting algorithm based on the divide and conquer strategy. This algorithm begins by splitting the array into two halves (sub-arrays) and continues splitting recursively till a sub-array is reduced to a single element, after which merging begins. During the merge operation, the sub-arrays are merged in sorted order into an auxiliary array.

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.

array : to be sorted. Example : [ 7, 3, 5, 2, 4, 1, 8, 6 ]
low : index of the first element i.e 0
high : index of the last element i.e length / size of array - 1 i.e 7

MergeSort ( array, low, 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 )

Steps showing the recursive splitting of the left sub-array

Step / Call Array Low High Check ( low < high ) Mid
1. MergeSort ( array, low, high ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 0 7 Yes 3
2. MergeSort ( array, low, mid ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 0 3 Yes 1
3. MergeSort ( array, low, mid ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 0 1 Yes 0
4. MergeSort ( array, low, mid ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 0 0 No -

Since low is not less than high, the recursive splitting of the left sub-array ends and the function returns
to call the next instruction i.e MergeSort ( array, mid + 1, high )

Steps showing the recursive splitting of the right sub-array of the call stack

Step / Call Array Low High Check ( low < high ) Mid
1. MergeSort ( array, mid + 1, high ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 1 1 No -

Since low is not less than high, the recursive splitting of the right sub-array ends and the function returns
to call the next instruction i.e 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 ( array, low, mid, 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.

Steps showing the merge of the left sub-array and the right sub-array of the array

Step / Call Array Low Mid High
1. Merge ( array, low, mid, high ) [ 7, 3, 5, 2, 4, 1, 8, 6 ] 0 0 1

After the first call to Merge, the sub-array [ low : high ] i.e array [ 0 : 1 ] gets sorted and becomes [ 3, 7, 5, 2, 4, 1, 8, 6 ].

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.

Merge Sort Implementation

``````
# 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 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 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(){

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 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

``````Unsorted array: 7 3 5 2 4 1 8 6
Sorted array using Merge-Sort: 1 2 3 4 5 6 7 8
``````