Merge Sort
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?
Code
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))
