Recursive merge sort in python 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] &lt; 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)
#&gt;&gt;&gt; 0 1 2 3 4 6 8 8 43


Thanks CR.
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) &lt;= 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 &lt; len(left) and right_index &lt; len(right):
        if left[left_index] &lt; 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) &lt;= 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)