# Merge Sort: implementation and analysis

def merge(left, right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 result += left[i:] result += right[j:] return result def mergesort(list): if len(list) < 2: return list middle = len(list) / 2 left = mergesort(list[:middle]) right = mergesort(list[middle:]) return merge(left, right) l = [ n for n in reversed(range(1,11)) ] print l print mergesort(l)

#### What’s going on

**mergesort()**keeps calling itself on two halved list until*eventually*- the list is just one element, and returns itself; control goes back to the last
**mergesort()**previously called, which now has values for**left**and**right**, and it is able to return**merge(left, right)** - The return value of
**merge(left, right)**is a new list which becomes the**left**or**right**on the parent**mergesort()**, until the very first one that will just return the final, sorted list.

Also note that this part

result += left[i:] result += right[j:]

is needed because at some point either **i** or **j** will be grater then their len(list), causing the while loop to terminate. However, every time the left branch is merged first it means that there are still elements on the right branch that are still to be added, and vice versa.

### Analysis

The number of times we can halve \( n \) before getting to 1 is \( \log(n) \), therefore we have \( \log(n) \) levels of depth.

For every level j we have \( 2^j \) subproblems, each one with \( \frac{n}{2^j} \) elements. This implies that the running time *is the same for every level*, since

Combining the two, the running time for Merge Sort results in \( O(n \log(n)) \).