Why that version of mergesort is faster

Question

Based on that answer here are two versions of merge function used for mergesort. Could you help me to understand why the second one is much faster. I have tested it for list of 50000 and the second one is 8 times faster (Gist).

def merge1(left, right):
    i = j = inv = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left[i:])

    merged += left[i:]
    merged += right[j:]
    return merged, inv

.

def merge2(array1, array2):
    inv = 0
    merged_array = []
    while array1 or array2:
        if not array1:
            merged_array.append(array2.pop())
        elif (not array2) or array1[-1] > array2[-1]:
            merged_array.append(array1.pop())
            inv += len(array2)
        else:
            merged_array.append(array2.pop())
    merged_array.reverse()
    return merged_array, inv

Here is the sort function:

def _merge_sort(list, merge):
    len_list = len(list)
    if len_list < 2:
        return list, 0
    middle = len_list / 2
    left, left_inv   = _merge_sort(list[:middle], merge)
    right, right_inv = _merge_sort(list[middle:], merge)
    l, merge_inv = merge(left, right)
    inv = left_inv + right_inv + merge_inv
    return l, inv

.

import numpy.random as nprnd
test_list = nprnd.randint(1000, size=50000).tolist()

test_list_tmp = list(test_list) 
merge_sort(test_list_tmp, merge1)

test_list_tmp = list(test_list) 
merge_sort(test_list_tmp, merge2)

Answer 1

Similar answer as kreativitea's above, but with more info (i think!)

So profiling the actual merge functions, for the merging of two 50K arrays,

merge 1

         311748 function calls in 15.363 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001   15.363   15.363 <string>:1(<module>)
        1   15.322   15.322   15.362   15.362 merge.py:3(merge1)
   221309    0.030    0.000    0.030    0.000 {len}
    90436    0.010    0.000    0.010    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

merge2

         250004 function calls in 0.104 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.001    0.001    0.104    0.104 <string>:1(<module>)
        1    0.074    0.074    0.103    0.103 merge.py:20(merge2)
    50000    0.005    0.000    0.005    0.000 {len}
   100000    0.010    0.000    0.010    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
   100000    0.014    0.000    0.014    0.000 {method 'pop' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'reverse' of 'list' objects}

So for merge1, it's 221309 len, 90436 append, and takes 15.363 seconds. So for merge2, it's 50000 len, 100000 append, and 100000 pop and takes 0.104 seconds.

len and append pop are all O(1) (more info here), so these profiles aren't showing what's actually taking the time, since going of just that, it should be faster, but only ~20% so.

Okay the cause is actually fairly obvious if you just read the code:

In the first method, there is this line:

inv += len(left[i:])

so every time that is called, it has to rebuild an array. If you comment out this line (or just replace it with inv += 1 or something) then it becomes faster than the other method. This is the single line responsible for the increased time.

Having noticed this is the cause, the issue can be fixed by improving the code; change it to this for a speed up. After doing this, it will be faster than merge2

inv += len(left) - i

Update it to this:

def merge3(left, right):
    i = j = inv = 0
    merged = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            inv += len(left) - i

    merged += left[i:]
    merged += right[j:]
    return merged, inv