# Python merge sort for a list containing distinct values

This code below is what I think should be the implementation of merge sort in Python and it works as expected. It sorts the given list, where we can safely assume that all values are distinct. But after considering some online implementations I am doubtful about mine. So the base question is "Is this even Merge sort?".

def merge(arr):
# base case
length = len(arr)
half = length//2
if length == 1 or length == 0:
return arr
# recursive case
firstHalf = merge(arr[:half])  # sort first half
secondHalf = merge(arr[half:])  # sort second half
length_firstHalf = len(firstHalf)
length_secondHalf = len(secondHalf)
sortedList = []

i, j = 0, 0  # variables for iteration
while i != length_firstHalf and j != length_secondHalf:  # add elements into the new array until either of then two sub arrays is completely traversed
if firstHalf[i] > secondHalf[j]:
sortedList.append(secondHalf[j])
j += 1
continue
if firstHalf[i] < secondHalf[j]:
sortedList.append(firstHalf[i])
i += 1
return(sortedList + firstHalf[i:] + secondHalf[j:])  # return the array after adding whats left of sub array which wasnt completely traversed

• @200_success thank you for the advice, the code is edited now Mar 12, 2019 at 21:06
• @200_success now its okay i believe Mar 12, 2019 at 21:10
• @200_success thank you for editing. much better now Mar 12, 2019 at 21:17

• The naming is quite unusual. The procedure you call merge does the merge sort, and should be called so. The merge phase of the merge sort is done by the

    while i != length_firstHalf and j != length_secondHalf:


loop and the subsequent return. It is advisable to factor it out into a standalone merge procedure. OTOH I don't endorse a complicated return expressions.

• It is unclear why do you limit yourself to the distinct values. The second if clause may be safely made into an else, and there is no more worries. Notice that your first comparison firstHalf[i] > secondHalf[j] is the way to handle duplicates.

• Computing half doesn't belong to the base case.

• As a nitpick, length == 1 or length == 0 is a long way to say length < 2.

• Using distinct values was the requirement in the question that i was asked to solve. I think if I add this if firstHalf[i] >= secondHalf[j] then it can handle duplicate values. Mar 13, 2019 at 5:04