Merge Sort

Posted on | In ,

Merge sort is a straightforward divide-and-conquer sorting algorithm. It requires $O(n)$ extra memory, unlike quick sort. However, it guarantees $O(n \log n)$ time complexity even in the worst case.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
def _mergeSort(lst, fromIdx, toIdx):
    if toIdx - fromIdx <= 1:
        return
    mid = int((toIdx + fromIdx)/2)
    _mergeSort(lst, fromIdx, mid)
    _mergeSort(lst, mid, toIdx)

    #Where extra space is needed.
    auxList = [0] * (toIdx - fromIdx)
    idx1 = fromIdx
    idx2 = mid
    for i in range(toIdx - fromIdx):
        if idx2 >= toIdx or idx1 < mid and lst[idx1] <= lst[idx2]:#choose idx1
            auxList[i] = lst[idx1]
            idx1 += 1
        elif idx1 >= mid or idx2 < toIdx and lst[idx2] < lst[idx1]:#choose idx2
            auxList[i] = lst[idx2]
            idx2 += 1
        else:
            print('Invalid situation')
            raise
    for i in range(toIdx - fromIdx):
        lst[i + fromIdx] = auxList[i]
        
def mergeSort(lst):
    return _mergeSort(lst, 0, len(lst))

#Test code
import random

if __name__ == "__main__":
    for i in range(1000):
        lst = []
        for j in range(1000):
            lst.append(random.randint(0,100))
        targetIdx = random.randint(0,len(lst) - 1)
        lst2 = list(lst)

        #Will crush the qsort
        #lst2[0] = 0

        mergeSort(lst2)
        if sorted(lst) != lst2:
            print('wrong result for qsort')
            raise
    print('Every thing done well!')