# Merge Sort Algorithm – C++, Java, and Python Implementation

Given an integer array, sort it using the merge sort algorithm.

## Merge sort Overview

Merge sort is an efficient sorting algorithm that produces a stable sort, which means that if two elements have the same value, they hold the same relative position in the sorted sequence as they did in the input. In other words, the relative order of elements with equal values is preserved in the sorted sequence. Merge sort is a comparison sort, which means that it can sort any input for which a less-than relation is defined.

## How Merge sort works?

Merge sort is a Divide and Conquer algorithm. Like all divide-and-conquer algorithms, merge sort divides a large array into two smaller subarrays and then recursively sort the subarrays. Basically, two steps are involved in the whole process:

1. Divide the unsorted array into `n` subarrays, each of size `1` (an array of size `1` is considered sorted).
2. Repeatedly merge subarrays to produce new sorted subarrays until only `1` subarray is left, which would be our sorted array.

The following diagram represents a top-down view of the recursive merge sort algorithm used to sort an `7`-element integer array:

Practice this algorithm

Following is the C, Java, and Python implementation of the merge sort algorithm:

## C

Output:

-50 -41 -34 -23 -21 -11 5 9 10 19 26 33 35 40 49

## Java

Output:

[-2, 0, 3, 5, 12, 18, 24]

## Python

Output:

[-2, 0, 3, 5, 12, 18, 24]

## Merge Sort Performance

The worst-case time complexity of merge sort is O(n.log(n)), where `n` is the size of the input. The recurrence relation is:

`T(n) = 2T(n/2) + cn = O(n.log(n))`

The recurrence basically summarizes the merge sort algorithm – Sort two lists of half the original list’s size and add the `n` steps taken to merge the resulting two lists.

The auxiliary space required by the merge sort algorithm is O(n) for the call stack.

Also See:

Iterative Merge Sort Algorithm (Bottom-up Merge Sort)

External Merge Sort Algorithm

References: https://en.wikipedia.org/wiki/Merge_sort

Rate this post

Average rating 4.82/5. Vote count: 219

No votes so far! Be the first to rate this post.

We are sorry that this post was not useful for you!

Tell us how we can improve this post?