Merge Sort
Merge sort is one of the fastest sorting algorithms. Many applications use some versions of merge sort in production. We have discussed algorithms that run in quadratic time like Bubble sort or Selection sort. Merge sort is way faster than all the quadratic sorting algorithms and runs in time.
Merge sort is a divide-and-conquer algorithm that recursively sorts parts of the given array and merges those together. The core of the algorithm is the efficient algorithm to merge two sorted arrays into a single sorted array. During its work, the merge sort algorithm splits the array into two parts. Then recursively sorts the first part. After which recursively sorts the second part. Then merges those two sorted arrays into one sorted array:
def merge(a, b):
i, j, res = 0, 0, [] # Index for a and b with resulting array
while i < len(a) or j < len(b): # While there are still elements left
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # If a[i] < b[j] => take a[i]
res.append(ai) # Add a[i] to result
i += 1 # Move to the next element
else: # If a[i] >= b[j] => take b[j]
res.append(bj) # Add b[j] to result
j += 1 # Move to the next element
return res
def merge_sort(a):
if len(a) <= 1: # Nothing to sort
return a # Return the initial array
l = merge_sort(a[: len(a) // 2]) # Sort the left part
r = merge_sort(a[len(a) // 2:]) # Sort the right part
return merge(l, r)At each stage, the algorithm takes the array, splits it into 2 parts, sorts those separately, and merges the resulting arrays into a new one. Note that all the previous algorithms discussed changed the initial array in place (modified it without creating a new one), while the merge sort algorithm creates a new array on each iteration. It’s quite challenging to make the merge sort algorithm perform in-place sorting. Can you tell why that’s the case?
Let’s simulate the algorithm on several arrays:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1]):merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([1, -1]):merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
- Back to
merge_sort([4, 1, -1])→ return[-1, 1, 4]
merge_sort([0, 2, 8]):merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([2, 8]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
- Back to
merge_sort([2, 8])→ return[2, 8]
- Back to
merge_sort([0, 2, 8])→ return[0, 2, 8]
- Back to
merge_sort([4, 1, -1, 0, 2, 8])→ return[-1, 0, 1, 2, 4, 8]
Challenge
Given an array of
n integers, you are asked to sort them in descending order using the Merge Sort algorithm.Input
The first line of the input contains a single integer
n (1 ≤ n ≤ 100 000).The next line contains
n space-separated integers Output
The program should print
n space-separated integers in descending order.Examples
Input | Output |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB