Mergesort with Python

Posted on

Question :

Mergesort with Python

I couldn’t find any working Python 3.3 mergesort algorithm codes, so I made one myself. Is there any way to speed it up? It sorts 20,000 numbers in about 0.3-0.5 seconds

``````def msort(x):
result = []
if len(x) < 2:
return x
mid = int(len(x)/2)
y = msort(x[:mid])
z = msort(x[mid:])
while (len(y) > 0) or (len(z) > 0):
if len(y) > 0 and len(z) > 0:
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
elif len(z) > 0:
for i in z:
result.append(i)
z.pop(0)
else:
for i in y:
result.append(i)
y.pop(0)
return result
``````

You can initialise the whole result list in the top level call to mergesort:

``````result = [0]*len(x)   # replace 0 with a suitable default element if necessary.
# or just copy x (result = x[:])
``````

Then for the recursive calls you can use a helper function to which you pass not sublists, but indices into `x`. And the bottom level calls read their values from `x` and write into `result` directly.

That way you can avoid all that `pop`ing and `append`ing which should improve performance.

The first improvement would be to simplify the three cases in the main loop: Rather than iterating while some of the sequence has elements, iterate while both sequences have elements. When leaving the loop, one of them will be empty, we don’t know which, but we don’t care: We append them at the end of the result.

``````def msort2(x):
if len(x) < 2:
return x
result = []          # moved!
mid = int(len(x) / 2)
y = msort2(x[:mid])
z = msort2(x[mid:])
while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:
result.append(z[0])
z.pop(0)
else:
result.append(y[0])
y.pop(0)
result += y
result += z
return result
``````

The second optimization is to avoid `pop`ping the elements. Rather, have two indices:

``````def msort3(x):
if len(x) < 2:
return x
result = []
mid = int(len(x) / 2)
y = msort3(x[:mid])
z = msort3(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
``````

A final improvement consists in using a non recursive algorithm to sort short sequences. In this case I use the built-in `sorted` function and use it when the size of the input is less than 20:

``````def msort4(x):
if len(x) < 20:
return sorted(x)
result = []
mid = int(len(x) / 2)
y = msort4(x[:mid])
z = msort4(x[mid:])
i = 0
j = 0
while i < len(y) and j < len(z):
if y[i] > z[j]:
result.append(z[j])
j += 1
else:
result.append(y[i])
i += 1
result += y[i:]
result += z[j:]
return result
``````

My measurements to sort a random list of 100000 integers are 2.46 seconds for the original version, 2.33 for msort2, 0.60 for msort3 and 0.40 for msort4. For reference, sorting all the list with `sorted` takes 0.03 seconds.

Code from MIT course. (with generic cooperator )

``````import operator

def merge(left, right, compare):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if compare(left[i], right[j]):
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < len(left):
result.append(left[i])
i += 1
while j < len(right):
result.append(right[j])
j += 1
return result

def mergeSort(L, compare=operator.lt):
if len(L) < 2:
return L[:]
else:
middle = int(len(L) / 2)
left = mergeSort(L[:middle], compare)
right = mergeSort(L[middle:], compare)
return merge(left, right, compare)
``````

``````def merge_sort(x):

if len(x) < 2:return x

result,mid = [],int(len(x)/2)

y = merge_sort(x[:mid])
z = merge_sort(x[mid:])

while (len(y) > 0) and (len(z) > 0):
if y[0] > z[0]:result.append(z.pop(0))
else:result.append(y.pop(0))

result.extend(y+z)
return result
``````

Take my implementation

``````def merge_sort(sequence):
"""
Sequence of numbers is taken as input, and is split into two halves, following which they are recursively sorted.
"""
if len(sequence) < 2:
return sequence

mid = len(sequence) // 2     # note: 7//2 = 3, whereas 7/2 = 3.5

left_sequence = merge_sort(sequence[:mid])
right_sequence = merge_sort(sequence[mid:])

return merge(left_sequence, right_sequence)

def merge(left, right):
"""
Traverse both sorted sub-arrays (left and right), and populate the result array
"""
result = []
i = j = 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

# Print the sorted list.
print(merge_sort([5, 2, 6, 8, 5, 8, 1]))
``````

As already said, `l.pop(0)` is a O(len(l)) operation and must be avoided, the above msort function is O(n**2). If efficiency matter, indexing is better but have cost too. The `for x in l` is faster but not easy to implement for mergesort : `iter` can be used instead here. Finally, checking `i < len(l)` is made twice because tested again when accessing the element : the exception mechanism (try except) is better and give a last improvement of 30% .

``````def msort(l):
if len(l)>1:
t=len(l)//2
it1=iter(msort(l[:t]));x1=next(it1)
it2=iter(msort(l[t:]));x2=next(it2)
l=[]
try:
while True:
if x1<=x2: l.append(x1);x1=next(it1)
else     : l.append(x2);x2=next(it2)
except:
if x1<=x2: l.append(x2);l.extend(it2)
else:      l.append(x1);l.extend(it1)
return l
``````

Loops like this can probably be speeded up:

``````for i in z:
result.append(i)
z.pop(0)
``````

Instead, simply do this:

``````result.extend(z)
``````

Note that there is no need to clean the contents of `z` because you won’t use it anyway.

A longer one that counts inversions and adheres to the `sorted` interface. It’s trivial to modify this to make it a method of an object that sorts in place.

``````import operator

class MergeSorted:

def __init__(self):
self.inversions = 0

def __call__(self, l, key=None, reverse=False):

self.inversions = 0

if key is None:
self.key = lambda x: x
else:
self.key = key

if reverse:
self.compare = operator.gt
else:
self.compare = operator.lt

dest = list(l)
working = [0] * len(l)
self.inversions = self._merge_sort(dest, working, 0, len(dest))
return dest

def _merge_sort(self, dest, working, low, high):
if low < high - 1:
mid = (low + high) // 2
x = self._merge_sort(dest, working, low, mid)
y = self._merge_sort(dest, working, mid, high)
z = self._merge(dest, working, low, mid, high)
return (x + y + z)
else:
return 0

def _merge(self, dest, working, low, mid, high):
i = 0
j = 0
inversions = 0

while (low + i < mid) and (mid + j < high):
if self.compare(self.key(dest[low + i]), self.key(dest[mid + j])):
working[low + i + j] = dest[low + i]
i += 1
else:
working[low + i + j] = dest[mid + j]
inversions += (mid - (low + i))
j += 1

while low + i < mid:
working[low + i + j] = dest[low + i]
i += 1

while mid + j < high:
working[low + i + j] = dest[mid + j]
j += 1

for k in range(low, high):
dest[k] = working[k]

return inversions

msorted = MergeSorted()
``````

Uses

``````>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l)
>>> s
[1, 2, 3, 4, 5]
>>> msorted.inversions
6

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key)
>>> s
['c', 'b', 'd', 'e', 'a']
>>> msorted.inversions
5

>>> l = [5, 2, 3, 1, 4]
>>> s = msorted(l, reverse=True)
>>> s
[5, 4, 3, 2, 1]
>>> msorted.inversions
4

>>> l = ['e', 'b', 'c', 'a', 'd']
>>> d = {'a': 10,
...      'b': 4,
...      'c': 2,
...      'd': 5,
...      'e': 9}
>>> key = lambda x: d[x]
>>> s = msorted(l, key=key, reverse=True)
>>> s
['a', 'e', 'd', 'b', 'c']
>>> msorted.inversions
5
``````