I have just implemented this merge_sort, and this is also my first algorithm implemented in Python, I am totally open to feedback about how to better use python.
I am using Arrays instead of lists - I did this intentionally, to have a more a performant data structure.
My understanding is that a List in python is backed by an array, therefore, the performance should be the same as arrays, the difference is a single type for the collection elements.
A Functional Thinking
Since I am not sure(not a Python master), but I need to ask: Is this merge sort a functional one?
At least in terms of no side effects and referential transparency, can we say, it is a FP merge sort, since I do not change the input?
from array import * def split_arr(arr): length = len(arr) / 2 return arr[:length], arr[length:] def merge(arr_i, arr_j): k = len(arr_i) + len(arr_j) arr_out = array('i') i = 0 j = 0 i_end = False j_end = False while k > 0: if not i_end: if not j_end and arr_i[i] < arr_j[j]: arr_out.append(arr_i[i]) i += 1 if i == len(arr_i): i_end = True elif not j_end and arr_i[i] > arr_j[j]: arr_out.append(arr_j[j]) j += 1 if j == len(arr_j): j_end = True else: arr_out.append(arr_i[i]) i += 1 if i == len(arr_i): i_end = True elif not j_end: arr_out.append(arr_j[j]) j += 1 if j == len(arr_j): j_end = True k -= 1 return arr_out def merge_sort(arr): length = len(arr) if length <= 1: return arr else: a1, a2 = split_arr(arr) return merge(merge_sort(a1), merge_sort(a2))