3
\$\begingroup\$

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))
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.