# Merge sort (Python)

### From LiteratePrograms

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

This article explains how to implement merge sort in Python.

Conceptually, merge sort works as follows:

- Divide the unsorted list into two sublists of about half the size
- Sort each of the two sublists
- 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>>=defmerge(left, right): result = [] i ,j = 0, 0whilei < len(left)andj < len(right):ifleft[i] <= right[j]: result.append(left[i]) i += 1else: 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:]returnresult

## 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>>=defmergesort(list):iflen(list) < 2:returnlistelse: middle = len(list) / 2 left = mergesort(list[:middle]) right = mergesort(list[middle:])returnmerge(left, right)

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

<<mergesort.py>>=merge mergesortif__name__ == "__main__":

## Execution result

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

Download code |