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.

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))

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