Python Merge Sort Implementation

Question

I doing some algorithm reviews and am soliciting opinions on my implementation of the Merge Sort in Python.

Anything from readability to optimization is fair game.

In particular, I am wondering if accessing the elements of a list using pop(0) somehow slows things down. I am doing this because I am not aware of a good way to peek into the last for the last element.

Note: The code works on both Python 3 and 2.

import math def merge(left, right): merge_result = [] while (len(left) > 0 and len(right) > 0): if left[0] > right[0]: merge_result.append(right.pop(0)) else: merge_result.append(left.pop(0)) while (len(left)): merge_result.append(left.pop(0)) while (len(right)): merge_result.append(right.pop(0)) return merge_result def merge_sort(array_to_be_sorted): if len(array_to_be_sorted) < 2: return array_to_be_sorted middle = math.floor(len(array_to_be_sorted) / 2) left = array_to_be_sorted[0:middle] right = array_to_be_sorted[middle:] return merge(merge_sort(left),merge_sort(right)) 

Answer 1

.pop(0) would remove the first element from a list - this is a \$O(n)\$ operation since everything after must "shift" (Time Complexity reference).

I would not pop from left and right subarrays and instead keep track of indexes in both the left and right lists:

def merge(left, right): merge_result = [] left_index = right_index = 0 while left_index < len(left) and right_index < len(right): if left[left_index] > right[right_index]: merge_result.append(right[right_index]) right_index += 1 else: merge_result.append(left[left_index]) left_index += 1 merge_result += left[left_index:] merge_result += right[right_index:] return merge_result 

And, if you are preparing for an interview, make sure to write this function from memory couple times - it'll persist in your memory pretty soon - focus on the pattern (using left and right indexes for merging), don't try to remember the code line-by-line.

Answer 2

General issues

Here

while (len(left) > 0 and len(right) > 0): .... 

you can write just

while len(left) > 0 and len(right) > 0: .... 

or even:

while left and right: ... 

Also,

while (len(right)): merge_result.append(right.pop(0)) 

above the second line is overintended. It should be

while len(right): merge_result.append(right.pop(0)) 

Here,

middle = math.floor(len(array_to_be_sorted) / 2) 

just do

middle = len(array_to_be_sorted) // 2 

Performance

This is my primary concern. Your implementation works correctly, but, alas, it's slow:

OP's mergesort in 4356 milliseconds. coderodde's mergesort in 700 milliseconds. Native sort in 33 milliseconds. OP's mergesort agrees with native sort: True coderodde's mergesort agrees with native sort: True 

As you can see, the native sort routine is unbeatable since it is implemented in native machine code (apart from being Timsort (as far as I know)). What comes to routine I provided, it runs in \$\Theta(n \log n)\$ time using a swapping array pattern: it creates an auxiliary array with the same contents as the actual array to sort and keeps alternating between the two. The idea is that, when merging, we do merge from one array to another, which avoids creating new smaller arrays to hold the left and right parts of the input range. All in all, I had this in mind:

import math import random import time def millis(): return int(round(time.time() * 1000)) def op_merge(left, right): merge_result = [] while left and right: if left[0] > right[0]: merge_result.append(right.pop(0)) else: merge_result.append(left.pop(0)) while len(left): merge_result.append(left.pop(0)) while len(right): merge_result.append(right.pop(0)) return merge_result def op_merge_sort(array_to_be_sorted): if len(array_to_be_sorted) < 2: return array_to_be_sorted middle = math.floor(len(array_to_be_sorted) / 2) left = array_to_be_sorted[0:middle] right = array_to_be_sorted[middle:] return op_merge(op_merge_sort(left), op_merge_sort(right)) def coderodde_merge(source_array, target_array, left_start_index, right_start_index, right_end_index): left_end_index = right_start_index # Just rename: left_index = left_start_index right_index = right_start_index target_array_index = left_start_index while left_index < left_end_index and right_index < right_end_index: if source_array[left_index] > source_array[right_index]: target_array[target_array_index] = source_array[right_index] right_index += 1 else: target_array[target_array_index] = source_array[left_index] left_index += 1 target_array_index += 1 while left_index < left_end_index: target_array[target_array_index] = source_array[left_index] target_array_index += 1 left_index += 1 while right_index < right_end_index: target_array[target_array_index] = source_array[right_index] target_array_index += 1 right_index += 1 def coderodde_merge_sort_impl(source_array, target_array, start_index, end_index): range_len = end_index - start_index if range_len < 2: return middle_index = start_index + range_len // 2 coderodde_merge_sort_impl(target_array, source_array, start_index, middle_index) coderodde_merge_sort_impl(target_array, source_array, middle_index, end_index) coderodde_merge(source_array, target_array, start_index, middle_index, end_index) def coderodde_merge_sort(array): aux_array = array[:] coderodde_merge_sort_impl(aux_array, array, 0, len(array)) def benchmark_op_mergesort(): start_time = millis() arr = op_merge_sort(array1) end_time = millis() print("OP's mergesort in", end_time - start_time, "milliseconds.") return arr def benchmark_coderodde_mergesort(): start_time = millis() coderodde_merge_sort(array2) end_time = millis() print("coderodde's mergesort in", end_time - start_time, "milliseconds.") def benchmark_native_sort(): start_time = millis() array3.sort() end_time = millis() print("Native sort in", end_time - start_time, "milliseconds.") def arrays_are_same(arr1, arr2): if len(arr1) != len(arr2): return False for i in range(len(arr1)): if arr1[i] != arr2[i]: return False return True array1 = [] for i in range(200_000): array1.append(random.randint(-1_000_000, 2_000_000)) array2 = array1[:] array3 = array1[:] array1 = benchmark_op_mergesort() benchmark_coderodde_mergesort() benchmark_native_sort() print("OP's mergesort agrees with native sort:", arrays_are_same(array1, array3)) print("coderodde's mergesort agrees with native sort:", arrays_are_same(array2, array3))