# Merge Sort In Pythonby Isai Damier, Android Engineer @ Google

```#=======================================================================
#  Author: Isai Damier
#  Title: Mergesort
#  Project: geekviewpoint
#  Package: algorithm.sorting
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Best = Average = Worst = O(nlog(n)).
#
#  Approach:
#   Merge sort is a divide and conquer algorithm. In the divide and
#   conquer paradigm, a problem is broken into pieces where each piece
#   still retains all the properties of the larger problem -- except
#   its size. To solve the original problem, each piece is solved
#   individually; then the pieces are merged back together.
#
#   For illustration, imagine needing to sort an array of 200 elements
#   using selection sort. Since selection sort takes O(n^2), it would
#   take about 40,000 time units to sort the array. Now imagine
#   splitting the array into ten equal pieces and sorting each piece
#   individually still using selection sort. Now it would take 400
#   time units to sort each piece; for a grand total of 10400 = 4000.
#   Once each piece is sorted, merging them back together would take
#   about 200 time units; for a grand total of 200+4000 = 4,200.
#   Clearly 4,200 is an impressive improvement over 40,000. Now
#   imagine greater. Imagine splitting the original array into
#   groups of two and then sorting them. In the end, it would take about
#   1,000 time units to sort the array. That's how merge sort works.
#
#  NOTE to the Python experts:
#     While it might seem more "Pythonic" to take such approach as
#
#         mid = len(aList) / 2
#         left = mergesort(aList[:mid])
#         right = mergesort(aList[mid:])
#
#     That approach take too much memory for creating sublists.
#=======================================================================
def mergesort( aList ):
_mergesort( aList, 0, len( aList ) - 1 )

def _mergesort( aList, first, last ):
# break problem into smaller structurally identical pieces
mid = ( first + last ) / 2
if first < last:
_mergesort( aList, first, mid )
_mergesort( aList, mid + 1, last )

# merge solved pieces to get solution to original problem
a, f, l = 0, first, mid + 1
tmp = [None] * ( last - first + 1 )

while f <= mid and l <= last:
if aList[f] < aList[l] :
tmp[a] = aList[f]
f += 1
else:
tmp[a] = aList[l]
l += 1
a += 1

if f <= mid :
tmp[a:] = aList[f:mid + 1]

if l <= last:
tmp[a:] = aList[l:last + 1]

a = 0
while first <= last:
aList[first] = tmp[a]
first += 1
a += 1
```
```import unittest
from algorithms import sorting

class Test( unittest.TestCase ):

def testMergesort( self ):
A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5]
sorting.mergesort( A )
for i in range( 1, len( A ) ):
if A[i - 1] > A[i]:
self.fail( "mergesort method fails." )
```