3
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ @200_success thank you for the advice, the code is edited now \$\endgroup\$ – Bill_Bates Mar 12 at 21:06
  • \$\begingroup\$ @200_success now its okay i believe \$\endgroup\$ – Bill_Bates Mar 12 at 21:10
  • \$\begingroup\$ @200_success thank you for editing. much better now \$\endgroup\$ – Bill_Bates Mar 12 at 21:17
2
\$\begingroup\$

To address your immediate concern, yes it is a merge sort.

  • 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.

\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Bill_Bates Mar 13 at 5:04

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.