Hadron DaVinci

Merge Sort Tutorial

14 May 2021 - Hadron DaVinci

Example

Sort the given array with Merge Sort:

A = [5, 2, 4, 6, 1, 3]
merge_sort(A)
assert(A) == [1, 2, 3, 4, 5, 6]

Method

Given if array has more than one item

1. half array
2. merge-sort first half
3. merge-sort second half
4. merge first half and second half

Complexity

Time Complexity: N log(N)
Space Complexity: N
Stable

Code

method1.py
method2.py