Why return value is 0 when use Mergesort in Python?

user_6213399 0
Viewed 70

I am making merge sort code but it does not sort. Do you see what's wrong with it?

def mergeSort(L):
   if len(L) == 1:
       return L
   else:
       # divide
       L1 = mergeSort(L[0:round(len(L)/2)])
       L2 = mergeSort(L[round(len(L)/2):len(L)])
    
       # merge
       i = 0
       j = 0
       K = []
       while i < len(L1) and j < len(L2):
           if L1[i] < L2[j]:
               K.append(L1[i])
               i=i+1
           else:
               K.append(L2[j])
               j=j+1
       return K

Input:

L = [1,2,5,7,8,0,10,21,32,53,16,16,48,59,64,53,75,52,42,21,98,76‌​]

Output:

L = [0]
mergesort merge python-3.x sorting python
3 Answers
while i < len(L1) and j < len(L2):

This doesn't look right to me. With this condition, the loop will end once either of i or j reaches the end of their respective list. There might still be elements in the other list that never get iterated over, as a result.

Try changing that and to an or, and add some checking to make sure that inter-list comparison only happens when neither list has been completely iterated yet:

    while i < len(L1) or j < len(L2):
        if i < len(L1) and (j == len(L2) or L1[i] < L2[j]):
            K.append(L1[i])
            i=i+1
        else:
            K.append(L2[j])
            j=j+1

Now your code outputs [0, 1, 2, 5, 7, 8, 10, 16, 16, 21, 21, 32, 42, 48, 52, 53, 53, 59, 64, 75, 76, 98].

user_9534820

Consider this line:

while i < len(L1) and j < len(L2):

For example, if all the elements in L1 are smaller than all the elements in L2 then this loop will put all the elements in L1 into the result K. The loop will then finish and all of L2 will be ignored. You need to mop up the remaining elements when this loop finishes. Add this line of code immediately after the loop:

K.extend(L1[i:] + L2[j:])

By the way, I found this by stepping through your code with a debugger, with input L=[2,1]. I found that when I only went through the while loop for one iteration, and since one element is added each loop iteration there could only be one element in the result. If you don't already know how to step through code with a debugger, now would be a good time to learn.

user_70084160

In while condition the "And" operation should have changed to "or" and then your problem is solved.

def merge_sort(L):
    if len(L) == 1:
        return L

    else:
        # divide
        L1 = merge_sort(L[0:round(len(L) / 2)])
        L2 = merge_sort(L[round(len(L) / 2):len(L)])

        # merge
        i = 0
        j = 0
        K = []
        while i < len(L1) or j < len(L2):
            if i < len(L1) and (j == len(L2) or L1[i] < L2[j]):
                K.append(L1[i])
                i = i + 1
            else:
                K.append(L2[j])
                j = j + 1
        return K

Now you will get the desired output and it will not show you zero.

user_165197820
Related