We want to sort an array with n elements. Merge-sort does this by breaking up the array into two-halves, sorting them separately and then combining the results.

# Merge-sort Algorithm

The first 2.5 minutes of the video above explain the merge-sort algorithm. The next 3 minutes (optional) compare merge-sort and quick-sort in one case where quick-sort's pivot choices get lucky, and another where quick-sort gets unlucky.

# GIF animation of Merge-sort

# Algorithm Steps

define mergesort(x):recursively sort first-half of xrecursively sort second-half of xmerge sorted halfs into single sorted array

# Run-time analysis

The easiest way to understand the run-time complexity of merge-sort is to ** look** at the recursion graph. There are O(

*log n*) layers in the tree, and each layer is size O(

*n*). Hence, the total algorithm is O(

*n log n*).

# Code (almost python)

define mergesort(x):""" Sort array using merge sort algorithm """# base caseif length(x) <= 1: return x# split from middle. mergesort each half. then mergemiddle = length(x)/2a = mergesort(x[:middle])b = mergesort(x[middle:])return merge(a, b)define merge(a, b):""" merge arrays a and b """c = list()while not empty(a) or not empty(b):# add smaller element to c and remove from original array# (handle boundary cases of a / b being empty)if empty(a) or (not empty(b) and a[0] <= b[0]):c.append(a[0])a.pop()else:c.append(b[0])b.pop()return c