**Merge sort** is a sorting algorithm that is trivial to apply and has a time complexity of $O(n * logn)$ for all conditions (`best case`

, `worst case`

and `average case`

). This algorithm is based on the divide and conquers strategy.

The sorting algorithm continuously splits a list into multiple sublists until each sublist has only one item left. It then merges those sublists into a sorted list.

## What is Merge Sort?

Merge Sort, considered to be the most efficient sorting algorithm, works on the principle ‘**Divide and Conquer**‘.

The algorithm can be divided into three parts :

**Divide**– It is the initial stage where the**midpoint**of the`array`

is found using $mid=start+(end-start)/2$**Conquer**– In this step, the array is divided into`subarrays`

, using the midpoint calculated. The process repeats itself recursively until all elements become single array elements.**Combine**– In this step, the**subarrays**formed are combined in**sorted order**.

## Example :

Sorting the array `[45, 22, 67, 14, 55, 38]`

using merge sort.

## Complexity Analysis of Merge Sort

Merge sort repeatedly divides the array into **two equally sized parts**.

Thus merge sort time complexity depends on the number of division stages.

The number of division stages is $log~2~n$.

On each merge stage, n elements are merged.

- Step 1 – $n × 1$
- Step 2 – $n/2 × 2$
- Step 3 – $n/4 × 4$

Merge Sort time complexity is calculated using time per division stage. Since the merge process has linear time complexity, for `n`

elements there will be $n * log~2~n$ division and merge stages.

Hence, regardless of the arrangement, the time complexity of Merge Sort is $O(nlogn)$

## Analysis of Merge Sort Time Complexity

### Best Case Time Complexity of Merge Sort

The best case scenario occurs when the elements are already sorted in **ascending order**.

If two sorted `arrays`

of size `n`

need to be merged, the minimum number of comparisons will be `n`

. This happens when all elements of the first array are less than the elements of the second array.

The best case time complexity of merge sort is $O(n*logn)$.

### Average Case Time Complexity of Merge Sort

The average case scenario occurs when the elements are **jumbled** (neither in ascending nor descending order). This depends on the number of comparisons.

The average case time complexity of merge sort is $O(n*logn)$.

### Worst Case Time Complexity of Merge Sort

The worst-case scenario occurs when the given array is sorted in **descending order** leading to the maximum number of comparisons.

In this case, for two sorted arrays of size `n`

, the minimum number of comparisons will be `2n`

.

The worst-case time complexity of merge sort is $O(n*logn)$.

## Analysis of Merge Sort Space Complexity

In merge sort, all elements are copied into an **auxiliary array** of size `N`

, where `N`

is the **number of elements present in the unsorted array**.

Hence, the space complexity for **Merge Sort** is $O(N)$.

## Learn more

## Conclusion

- Merge sort is a reliable sorting algorithm that uses a ‘
**divide and conquers**‘ paradigm. - Initially, it divides the problem into sub-problems and solves them individually.
- Then, it combines the results of sub-problems to get the solution to the original problem.
- Merge sort is a
**recursive sorting algorithm**. - The recurrence relation of merge sort is $T(n) = 2T(n/2) + θ(n)$.
- The time complexity of merge sort is
- Best Case: $O(n*logn)$
- Average Case: $O(n*logn)$
- Worst Case: $O(n*logn)$

- The space complexity of
**merge sort**is $O(n)$.