``````from __future__ import annotations

def merge(left_half: list, right_half: list) -> list:
"""Helper function for mergesort.

>>> left_half = [-2]
>>> right_half = [-1]
>>> merge(left_half, right_half)
[-2, -1]

>>> left_half = [1,2,3]
>>> right_half = [4,5,6]
>>> merge(left_half, right_half)
[1, 2, 3, 4, 5, 6]

>>> left_half = [-2]
>>> right_half = [-1]
>>> merge(left_half, right_half)
[-2, -1]

>>> left_half = [12, 15]
>>> right_half = [13, 14]
>>> merge(left_half, right_half)
[12, 13, 14, 15]

>>> left_half = []
>>> right_half = []
>>> merge(left_half, right_half)
[]
"""
sorted_array = [None] * (len(right_half) + len(left_half))

pointer1 = 0  # pointer to current index for left Half
pointer2 = 0  # pointer to current index for the right Half
index = 0  # pointer to current index for the sorted array Half

while pointer1 < len(left_half) and pointer2 < len(right_half):
if left_half[pointer1] < right_half[pointer2]:
sorted_array[index] = left_half[pointer1]
pointer1 += 1
index += 1
else:
sorted_array[index] = right_half[pointer2]
pointer2 += 1
index += 1
while pointer1 < len(left_half):
sorted_array[index] = left_half[pointer1]
pointer1 += 1
index += 1

while pointer2 < len(right_half):
sorted_array[index] = right_half[pointer2]
pointer2 += 1
index += 1

return sorted_array

def merge_sort(array: list) -> list:
"""Returns a list of sorted array elements using merge sort.

>>> from random import shuffle
>>> array = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> shuffle(array)
>>> merge_sort(array)
[-200, -10, -2, 3, 11, 99, 100, 100000]

>>> shuffle(array)
>>> merge_sort(array)
[-200, -10, -2, 3, 11, 99, 100, 100000]

>>> array = [-200]
>>> merge_sort(array)
[-200]

>>> array = [-2, 3, -10, 11, 99, 100000, 100, -200]
>>> shuffle(array)
>>> sorted(array) == merge_sort(array)
True

>>> array = [-2]
>>> merge_sort(array)
[-2]

>>> array = []
>>> merge_sort(array)
[]

>>> array = [10000000, 1, -1111111111, 101111111112, 9000002]
>>> sorted(array) == merge_sort(array)
True
"""
if len(array) <= 1:
return array
# the actual formula to calculate the middle element = left + (right - left) // 2
# this avoids integer overflow in case of large N
middle = 0 + (len(array) - 0) // 2

# Split the array into halves till the array length becomes equal to One
# merge the arrays of single length returned by mergeSort function and
# pass them into the merge arrays function which merges the array
left_half = array[:middle]
right_half = array[middle:]

return merge(merge_sort(left_half), merge_sort(right_half))

if __name__ == "__main__":
import doctest

doctest.testmod()
``````

#### Merge Sort

R
M
A
E
R
G
K
w
L
and 42 more contributors

#### Problem Statement

Given an array of n elements, write a function to sort the array

#### Approach

• Find a mid point and divide the array into to halves based on the mid point
• Recursively call the merge sort function for both the halves
• Merge the two sorted halves to get the sorted array

#### Time Complexity

`O(n log n)`

`O(n)`

#### Example

``````arr = [1, 3, 9, 5, 0, 2]

Divide the array in two halves [1, 3, 9] and [5, 0, 2]

Recursively call merge sort function for both these halves which will provide sorted halves
=> [1, 3, 9] & [0, 2, 5]

Now merge both these halves to get the sorted array [0, 1, 2, 3, 5, 9]
``````