Merge Sort

Intro

In computer science, merge sort (also commonly spelled mergesort) is an efficient, general-purpose, comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Definition

Conceptually, a merge sort works as follows:

1) Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).

2) Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Details

Class: Sorting algorithm
Data structure: Array
Worst-case performance: O(n log n)
Best-case performance: O(n log n) typical, O(n) natural variant
Average performance: O(n log n)
Worst-case space complexity:</1b> О(n) total, O(n) auxiliary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

from collections import deque
def merge_sort(lst):
    if len(lst) <= 1:
        return lst
    def merge(left, right):
        merged,left,right = deque(),deque(left),deque(right)
        while left and right:
            # deque popleft is also O(1)
            merged.append(left.popleft() if left[0] <= right[0] else right.popleft())  
        merged.extend(right if right else left)
        return list(merged)
    middle = int(len(lst) // 2)
    left = merge_sort(lst[:middle])
    right = merge_sort(lst[middle:])
    return merge(left, right)