Sort an Array - Leetcode 912 - Python

0:00 - Read the problem
0:50 - Drawing Explanation
8:45 - Coding Explanation

leetcode 912

#neetcode #leetcode #python

[NeetCodeIO]

Ok, I'm still traveling but I had already recorded this one a while back and just edited it.

[tunguyenxuan]

At 16:00, the code must be arr[i] = left[j]. The solution will actually work if you put it nums[i] = left[j] as you will assign nums to arr, but for the correctness, it must be arr inside merge function

[HoppyGamer]

One of the cleanest explainations of Merge Sort on YT

[DmitriyKl]

For those struggling to understand this solution, there's actually a slightly more straightforward way that was easier for me to understand. The overall approach is the same, there are 3 distinct steps:
1 - check if base case
2 - sort left and right halves
3 - merge sorted halves

the solution becomes:

# base case - array already sorted because len is <= 1
if len(nums) <= 1:
return nums

# sort left and right halves
mid_idx = len(nums) // 2 # calculate mid idx
left = # sort from 0 to mid idx (non-inclusive)
right = # sort from mid idx to right

# merge sorted halves
l_idx, r_idx = 0, 0
# new array to store ans but you can overwrite nums if you want
ans = []

# while either half still has nums left
while l_idx < len(left) or r_idx < len(right):
# if right half is exhausted OR (left half is not exhausted AND left num is less than right num)
if r_idx >= len(right) or l_idx < len(left) and left[l_idx] < right[r_idx]:
ans.append(left[l_idx])
l_idx+=1
# left half is not exhausted or right num < left num
else:
ans.append(right[r_idx])
r_idx+=1

return ans

[rahulsbhatt]

Thanks, had to revise this after seeing today's daily.

[adrianfrankowski]

You can precalculate len(left) and len(right) in merge function to make it a little bit faster.

[aliramazani]

Great job. However, the code below is slightly more efficient than your code because it performs all operations on the original list instead of creating new lists 'left' and 'right'. Overall, it was great to learn your approach as well.


def mergeSort(arr):
if len(arr) > 1:

# Finding the mid of the array
mid = len(arr)//2

# Dividing the array elements
L = arr[:mid]

# Into 2 halves
R = arr[mid:]

# Sorting the first half
mergeSort(L)

# Sorting the second half
mergeSort(R)

i = j = k = 0

# Copy data to temp arrays L[] and R[]
while i < len(L) and j < len(R):
if L[i] <= R[j]:
arr[k] = L[i]
i += 1
else:
arr[k] = R[j]
j += 1
k += 1

# Checking if any element was left
while i < len(L):
arr[k] = L[i]
i += 1
k += 1

while j < len(R):
arr[k] = R[j]
j += 1
k += 1

[cosepeter]

Your explanations are a thing of beauty ❤

[DimaLifeIsGood]

Nice, explanation of concept, simplicity of code is amazing, thank you for doing it :)

[degamer]

I used heapsort. Do you recommend knowing the other algorithms by heart like Mergesort, Quicksort, etc.. for interviews?

[khyunwoo]

this question was asked inside the "insertion sort" lesson on neetcode D:

[TheSiddhaartha]

The two arrays in *merge* method, still overwrite the *nums* array. In python, array slice copies by reference and not value. So better use .copy after slice eg arr[L:M+1].copy(). Otherwise answers are incorrect on computer. Maybe LeetCode accepted it with some sort of inbuilt conversion but Python interpreter gave incorrect results. So I used .copy() which solved the problem.

[mufaddaltatiwala]

You don't need to pass arr as an argument to the merge and mergeSort methods since they are already inside the sortArray, instead you can simply modify the nums array from both these methods and return nums in the end

[sarvesh]

I was waiting for your video. Great explanation as always 🔥🔥

[mahendrakoteri]

I did try Quick Sort but still got TLE..
so here I am

[urr]

I passed this problem on leetcode using quick sort. just randomly choose pivot and randomly separate elements with same key. It's quite inefficient though.

[hasibqureshi]

it is not that official channel. but videos are same. how .? no copy right issue?

[dushldp]

Why is i initialized with L and not 0. what is the problem if we initialize i = 0?

[mirshodoripov]

why is not Quicsort working for this problem?

[valorantfever]

Heap sort is not better than merge/quick overall, but its memory efficient. You should have gone for heap sort bro :(