Run time error in merge sort progran

#1

Can you fix the error ?

#2

Hey @amanbh_123, can you please upload your code on google drive and share the link over here ? I will have to look at the code to resolve your doubt and check the error !

Thanks ! :slight_smile:

#3

This is the code : https://drive.google.com/file/d/1tHsulHnXW85YfuminxM847qYx5pEB9dd/view?usp=sharing

#4

Hey @amanbh_123, I analysed your code in detail and found out that you have not followed the input format correctly. We need to take input of array in a single line whereas you were taking input of each element of the array (arr) in a different line. I have modified your code using a single line for input i.e. :

arr = [int(i) for i in input().split()]

Then there was TLE i.e. Time Limit Exceeded error coming. So for that I saw that you have initialised an out array and initialised it with all zeros (Which was increasing the time complexity or taking unnecessary time). Instead we could directly append values to that array without initialising the complete array with 0 in the merge() function. Here is your final code :

def merge(arr, si, mid, ei):
    size = ei - si + 1
   # mid = (si + ei)//2
    out = []
  #  for i in range(size):
  #      out.append(0)
    i, j, k = si, mid + 1, 0
    while (i <= mid and j <= ei):
        if (arr[i] < arr[j]):
            out.append(arr[i])
            k += 1
            i += 1

        else:
            out.append(arr[j])
            k += 1
            j += 1

    while i <= mid:
        out.append(arr[i])
        k += 1
        i += 1

    while j <= ei:
        out.append(arr[j])
        k += 1
        j += 1

    m = 0
    i = si
    while i <= ei:
        arr[i] = out[m]
        m += 1
        i += 1


def merge_sort(arr, si, ei):
    if si >= ei:
        return
    mid = (si + ei)//2
    merge_sort(arr, si, mid)
    merge_sort(arr, mid + 1, ei)
    merge(arr, si, mid, ei)

N = int(input())
arr = [int(i) for i in input().split()]
#for i in range(N):
#    temp = int(input())
#    arr.append(temp)

si = 0
ei = N - 1
merge_sort(arr, si, ei)
for i in range(N):
    print(arr[i], end = " ")

I hope this clears your doubt !
Please mark the doubt as resolved in your doubts section ! :slightly_smiling_face:
Happy Learning ! :slight_smile: