A Merge Sort implementation for efficiency

Question

This is my version of mergesort.

# mergesort
def merge(items, low, mid, high):
 left = [items[i] for i in range(low, mid + 1)]
 right = [items[i] for i in range(mid + 1, high + 1)]
 left.append(4444444444444444444444)
 right.append(4444444444444444444444)
 i = 0
 j = 0
 for k in range(low, high + 1):
 if left[i] < right[j]:
 items[k] = left[i]
 i += 1
 else:
 items[k] = right[j]
 j += 1
def mergesort(items,low, high):
 mid = int(low + (high - low) / 2)
 if low < high:
 mergesort(items, low, mid)
 mergesort(items, mid + 1, high)
 merge(items, low, mid, high)
if __name__ == "__main__":
 a = [6, 5, 4, 3, 2, 1]
 print(mergesort(a, 0, len(a) - 1))

I ran a test with input size of 1000000 in reverse order with a step of 1 i.e range(int(1e6), 1, -1) or range(1000000, 1, -1) and got the following results

6999991 function calls (4999995 primitive calls) in 9.925 seconds
 Ordered by: internal time
 List reduced from 9 to 8 due to restriction <8>
 ncalls tottime percall cumtime percall filename:lineno(function)
 999998 6.446 0.000 8.190 0.000 test.py:3(merge)
1999997/1 1.735 0.000 9.925 9.925 test.py:19(mergesort)
 999998 0.821 0.000 0.821 0.000 test.py:4(<listcomp>)
 999998 0.740 0.000 0.740 0.000 test.py:5(<listcomp>)
 1999996 0.183 0.000 0.183 0.000 {method 'append' of 'list' objects}
 1 0.000 0.000 9.925 9.925 {built-in method builtins.exec}
 1 0.000 0.000 9.925 9.925 <string>:1(<module>)
 1 0.000 0.000 0.000 0.000 {built-in method builtins.len}

I would love to optimize the code and if possible, eliminate the copies.

• theProgrammer: Python3. make sure to convert to int that is range(int(ie6), 1, -1) or rather use range(1000000, 1 -1)

Answer 1

Some comments:

• Include a convenience function that takes only a list, i.e., where you don't need to provide the bounds.
• Don't fight Python's inclusive-start exclusive-stop paradigm and naming.
• Write docstrings to explain what the parameters mean, especially if you use unusual stuff.
• Don't compute mid when you don't have to anyway.
• Compute mid with integer division and from the sum (Python's ints don't overflow).
• Don't reimplement slicing.
• You can easily do it with copying out just the left part.
• For benchmarking, I'd suggest to randomly shuffle the list instead of using a reverse-sorted list. I suspect you did the latter because you thought it's a worst case, but for example for Python's built-in sorting algorithm Timsort, it's a "best case", taking only linear time. And other algorithms might also be unrealistically affected (either faster or slower than for the typical case).
• Don't write an unstable merge sort, that's a sin :-P
• 4444444444444444444444 is unsafe. What if the list has items larger than that?

Here's my version of it, it's about three times as fast as yours both on reverse-sorted and on shuffled lists (tested with 100,000 items).

def merge(items, start, mid, stop):
 """Merge sorted items[start:mid] and items[mid:stop] into items[start:stop]."""
 for left in items[start:mid]:
 while mid < stop and items[mid] < left:
 items[start] = items[mid]
 start += 1
 mid += 1
 items[start] = left
 start += 1
def mergesort_slice(items, start, stop):
 """Sort items[start:stop]."""
 if stop - start > 1:
 mid = (start + stop) // 2
 mergesort_slice(items, start, mid)
 mergesort_slice(items, mid, stop)
 merge(items, start, mid, stop)
def mergesort(items):
 mergesort_slice(items, 0, len(items))

• val - disappointed in SE: "Python's ints don't overflow" what do they do instead? Extend to bigger size?
• Peter Cordes: @valsaysReinstateMonica: yes, they're objects that are compact-ish for values <= 2^30, and otherwise grow to as many BigInt chunks as needed to represent the value. Why do ints require three times as much memory in Python? / Why is 2 * x * x faster than 2 * ( x * x ) in Python 3.x, for integers?. I think Python2 had a fixed-width integer type, but Python3 doesn't.

Answer 2

These lines:

 left = [items[i] for i in range(low, mid + 1)]
 right = [items[i] for i in range(mid + 1, high + 1)]

Can be replaced with the built-in range operations on lists:

 left = items[low : mid + 1]
 right = items[mid + 1 : high + 1]

That should give you a slight speed-up on its own.

There isn't a great way to eliminate the copies without doing a lot of shifting, which would eliminate any speed benefits.

You might be able to squeeze a little extra performance out by altering your base case to explicitly handle sub-arrays of size 2, so you don't have to send single-element ranges through the whole merge process when you could instead just check if they are in order, and, if not, swap them.

Answer 3

From an optimization perspective, you can't totally avoid copying for mergesort (i.e. modify the list fully in place). What you can do, which should help, is generate one new list once using generators, thus avoiding constant allocations:

def mergesort_rec(items, low, high, is_top=True):
 if low + 1 == high:
 yield items[low] # Base case
 yield None # Avoid catching StopIteration
 return
 mid = int((low + high) / 2) # Equivalent to your code but more common definition of avg
 gen_left = mergesort_rec(items, low, mid, False)
 gen_right = mergesort_rec(items, mid, high, False)
 next_left = next(gen_left)
 next_right = next(gen_right)
 while True:
 if next_left is not None and next_right is not None:
 if next_left < next_right:
 yield next_left
 next_left = next(gen_left)
 else:
 yield next_right
 next_right = next(gen_right)
 elif next_right is not None:
 yield next_right
 next_right = next(gen_right)
 elif next_left is not None:
 yield next_left
 next_left = next(gen_left)
 else:
 break
 # You could avoid this with excepting StopIteration but I find this easier
 if not is_top:
 yield None

You can wrap this in a more user-friendly form factor and return it as a new list or modify in-place if that is needed:

def mergesorted(items):
 return [x for x in mergesort_rec(items, 0, len(items))]
def mergesort(items):
 items[:] = [x for x in mergesort_rec(items, 0, len(items))]

For your approach & code, I would suggest the following:

1. Don't use magic numbers (4444...). With python you could use a sentinel value such as None, or better yet, check your bounds explicitly.

2. Give the entry-point default values so the user isn't expected to give you the bounds, which could easily be off by one:

def mergesort(items, low=0, high=None):
 if high is None:
 high = len(items) - 1