# Merge Sort

- Merge Sort Algorithm
- Merge Sort Example
- Merge Sort Algorithm Implementation
- Merge Sort Algorithm Complexity

Merge sort is one of the most popular and efficient sorting algorithms. It is based on the principle of the divide and conquer algorithm. It works by dividing the array into two halves repeatedly until we get the array divided into individual elements. An individual element is a sorted array in itself. Merge sort repeatedly merges these small sorted arrays to produce larger sorted subarrays until we get one final sorted array. It is widely used in e-commerce applications.

## Merge Sort Algorithm

Top-down merge sort approach starts from the top with the full array and proceeds downwards to individual elements with recursion.

Suppose we have an unsorted array `A[]`

containing `n`

elements.

`MergeSort()`

##### Take two variables

`beg`

&`end`

then store the index of starting element and ending element.##### Find the middle point of the array to divide it into two halves using the formula

`mid =(beg+end)/2`

.##### Break the array into two parts

`arr[beg, .... , mid]`

and`arr[mid+1, .... , end]`

.##### Repeatedly divide the array into subarrays with single elements using recursion.

##### Call the merge function to start building the sorted array.

`Merge()`

##### Initialize the auxiliary array

`output`

to store the sorted output.##### Initialize 3 pointers

`i`

,`j`

&`k`

.`i`

points to the beginning of the first subarray`beg`

.

`j`

points to the beginning of the second subarray`mid+1`

.

`k`

initialized with`beg`

maintains the current index of sorted array`output`

.##### Until we reach the end of

`arr[beg, .... ,mid]`

or`arr[mid+1, .... ,end]`

subarray, we pick the smaller value among elements at index`i`

&`j`

and insert into`output`

.##### Pick the remaining elements and insert them into

`output`

once one of the arrays is exhausted.##### Copy

`output`

into`arr[beg, ... , end]`

.

## Merge Sort Example

Suppose we have the array: `(5,3,4,2,1,6)`

. We will sort it using the merge sort algorithm.

Action | `(5,3,4,2,1,6)` |
`mergesort(0,5)` |
---|---|---|

`divide` |
`(5,3,4) (2,1,6)` |
`mergesort(0,2) mergesort(3,5)` |

`divide` |
`(5,3) (4) (2,1) (6)` |
`mergesort(0,1) mergesort(2,2) mergesort(3,4) mergesort(5,5)` |

`divide` |
`(5) (3) (4) (2) (1) (6)` |
Array broken to individual elements |

`merge` |
`(3,5) (4) (1,2) (6)` |
`merge(0,1) merge(2,2) merge(3,4) merge(5,5)` |

`merge` |
`(3,4,5) (1,2,6)` |
`merge(0,2) merge(3,5)` |

`merge` |
`(1,2,3,4,5,6)` |
`merge(0,5)` |

We get the sorted array - `(1 2 3 4 5 6)`

## Merge Sort Algorithm Implementation

```
#include<iostream>
using namespace std;
void merge(int arr[], int beg, int mid, int end) {
int output[end - beg + 1];
int i = beg, j = mid + 1, k = 0;
// add smaller of both elements to the output
while (i <= mid && j <= end) {
if (arr[i] <= arr[j]) {
output[k] = arr[i];
k += 1; i += 1;
}
else {
output[k] = arr[j];
k += 1; j += 1;
}
}
// remaining elements from first array
while (i <= mid) {
output[k] = arr[i];
k += 1; i += 1;
}
// remaining elements from the second array
while (j <= end) {
output[k] = arr[j];
k += 1; j += 1;
}
// copy output to the original array
for (i = beg; i <= end; i += 1) {
arr[i] = output[i - beg];
}
}
void mergeSort(int arr[], int beg, int end) {
if (beg < end) {
int mid = (beg + end) / 2;
//divide and conquer
mergeSort(arr, beg, mid); // divide : first half
mergeSort(arr, mid + 1, end); // divide: second half
merge(arr, beg, mid, end); // conquer
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
mergeSort(arr, 0, n - 1); // Sort elements in ascending order
cout << "Output array: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
```

## Merge Sort Algorithm Complexity

### Time Complexity

- Average Case

Merge sort is a recursive algorithm. The following recurrence relation gives the time complexity expression for Merge sort.

```
T(n) = 2T(n/2) + θ(n)
```

This result of this recurrence relation gives `T(n) = nLogn`

.We can also see it as an array of size n being divided into a maximum of `Logn`

parts, and merging of each part takes `O(n)`

time.

Hence the time complexity is of the order of [Big Theta]: `O(nLogn)`

.

- Worst Case

The worst-case time complexity is [Big O]: `O(nLogn)`

.

- Best Case

The best-case time complexity is [Big Omega]: `O(nLogn)`

. It is the same as the worst-case time complexity.

### Space Complexity

Space Complexity for Merge Sort algorithm is `O(n)`

because `n`

auxiliary space is required for storing the sorted subarray in the auxiliary array.