# Merge sort (Python)

Other implementations: ACL2 | C | C++ | dc | Eiffel | Erlang | Haskell | Java | JavaScript | Lisp | OCaml | Oz | Perl | Prolog | Python | Ruby | Scheme

Conceptually, merge sort works as follows:

1. Divide the unsorted list into two sublists of about half the size
2. Sort each of the two sublists
3. Merge the two sorted sublists back into one sorted list.

The `merge()` method merges the two sorted sublists. The `mergesort()` method, which runs recursively, divides the unsorted lists into two sublists and sorts each sublist.

## The `merge()` method

Given two sublists `left` and `right`, the `merge()` method merges two sublists into an ordered list. The `result` list contains the whole elements in both sublists. `i` is the index of the `left` list, and `j` is the index of the `right` list. We continually copy the smaller value between `left[i]` and `right[j]` into the result list and advance that value's index.

```<<merge>>=
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
```

When we met an end in either sublist, we simply copy the remaining portion to the result. Note that both `left` and `right` sublists are already in sorted order and we do not have to re-order the remaining portion of a sublist.

```<<merge>>=
result += left[i:]
result += right[j:]
return result```

## The `mergesort()` method

The `mergesort()` method is a recursive divide-and-conquer algorithm.

• Boundary condition: If an input has less than two elements, it simply returns the input because there is no need to sort less than two elements.
• Recursive condition: If an input has more than one elements, it divides the input into two sublists and recursively run `mergesort()` methods to sort each sublist. Then it merges two sublists using `merge()` method.
```<<mergesort>>=
def mergesort(list):
if len(list) < 2:
return list
else:
middle = len(list) / 2
left = mergesort(list[:middle])
right = mergesort(list[middle:])
return merge(left, right)```

Here comes the whole source code with an integer list for an example.

```<<mergesort.py>>=
merge
mergesort
if __name__ == "__main__":
print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])
```

## Execution result

```crypto@crypto ~\$ python mergesort.py
[0, 1, 2, 3, 4, 4, 4, 5, 6, 7, 8, 9]
```