Recursive merge sort in python

Question

I'm very new to python, however not new to programming as I've been doing C for some time.

So here is my practice of a merge sort, I looked at other questions however they were many more lines compared to mine. Which leaves me to believe I'm doing something wrong.

I come here to look for best practices in python, and I mean the best of the best. I want to know all the little details! Most importantly if there is anyway to shorten code without sacrificing efficiency.

#!/usr/bin/python
def merge_sort(array):
 ret = []
 if( len(array) == 1):
 return array;
 half = len(array) / 2
 lower = merge_sort(array[:half])
 upper = merge_sort(array[half:])
 lower_len = len(lower)
 upper_len = len(upper)
 i = 0
 j = 0
 while i != lower_len or j != upper_len:
 if( i != lower_len and (j == upper_len or lower[i] < upper[j])):
 ret.append(lower[i])
 i += 1
 else:
 ret.append(upper[j])
 j += 1
 return ret
array = [4, 2, 3, 8, 8, 43, 6,1, 0]
ar = merge_sort(array)
print " ".join(str(x) for x in ar)
#>>> 0 1 2 3 4 6 8 8 43

Thanks CR.

Answer 1

First of all, there is a bug in the code - if an array is empty, you'll get a "maximum recursion depth exceeded" error. Improve your base case handling:

if len(array) <= 1:
 return array

Other improvements:

• the merging logic can be simplified - loop while where are elements in both arrays and append what is left after the loop
• extract the merging logic into a separate merge() function
• improve the variable naming - e.g. use left_index and right_index as opposed to i and j, result instead of ret
• no need to enclose if conditions into outer parenthesis
• Python 3 compatibility:
  • use print() as a function instead of a statement
  • use // for the floor division

Improved version:

def merge(left, right):
 """Merge sort merging function."""
 left_index, right_index = 0, 0
 result = []
 while left_index < len(left) and right_index < len(right):
 if left[left_index] < right[right_index]:
 result.append(left[left_index])
 left_index += 1
 else:
 result.append(right[right_index])
 right_index += 1
 result += left[left_index:]
 result += right[right_index:]
 return result
def merge_sort(array):
 """Merge sort algorithm implementation."""
 if len(array) <= 1: # base case
 return array
 # divide array in half and merge sort recursively
 half = len(array) // 2
 left = merge_sort(array[:half])
 right = merge_sort(array[half:])
 return merge(left, right)

• Oscar Smith: This is also about 20% faster with pypy (similar on Cpython
• llazzaro: what about the slice operation complexity? I think is O(k).
• joydeep bhattacharjee: extend is faster in terms of byte code hence it would be better to have result.extend(left[left_index:]) instead of +=