Python: MergeSort algorithm explained

Merge Sort algorithm explained, and how to write a Merge Sort algorithm implementation in Python, includes example code.

PYTHON SORTING ALGORITHMS

#Python

[perfectMind]

I am not sure if someone else pointed out to this problem earlier (didn't read all comments), but I had to change merge function, exactly I had to change the first 2 lines to the following:

L = A[first:middle+1]
R = A[middle+1:last+1]

Otherwise if my array has an odd size it wouldn't correctly sort it. If you have a closer look at it it does make sense, in mergeSort function we included the middle element in the left part of the array but in merge function (because of python syntax) the middle element is included in the right side.
Try this example: A = [4, 1, 5, 3, 7] to check.

Thanks for the video.

[billchen]

Joe explains merge sort so clearly, I got it. You are an awesome teacher.

[uppubhai]

Starting music feels a mission starting in cod modwen warfare

[Sustainability-for-future]

I was reading my book by N.Miller and L Ranum for hours and hours. thanks for your 10min video it makes sense now. much easier to understand by watching a video rather than reading books. Top of it the English my second language...so your video helped me very much.

[kaushilkundalia]

After days or research, i wasn't able to fully understand merge sort. But all thanks to you sir, you made it very easy and clear ! Thanks a lot !!

[thatsjustjohn]

Using is a very very poor decision for any programmer. Why would you not use the length to know the end of the list?

[akash-kumar]

Always return to same video. Very well explained. Probably watching it for 10th time.

[piyushsharma]

Clear and concise explanation .The starting and ending sound is similar to 90's Bollywood action movies

[kumark]

A methodical sort of the explanation before sorting. Very well explained

[levix]

When separating arrays going to end, array(L) got slice L[first(0):middle(0)] = []!!!!
You have to in calling merge add to middle + 1 ~ merge(A, first, middle + 1, last) or to slice add follow
L[first: middle + 1]
R[middle + 1:last + 1]

[vincentluong]

Using your videos and playlists to prep for interviews :). Great stuff

[josephbrown]

Great explanation of merge sort! You really don't have to add a big faked number at the end tho, just a couple more if's will cover it:
def merge(left, right, result):
i = j = 0
for k in range(0, len(result)):
if j >= len(right):
result[k:len(result)] = left[i:len(left)]
break
elif i >= len(left):
result[k:len(result)] = right[j:len(left)]
break
elif left[i] < right[j]:
result[k] = left[i]
i+=1
else:
result[k] = right[j]
j+=1

[rahmounioussama]

thanks man, this is still valid for 2024

[AppleBoy]

Visual and clear. Helped me understand the concepts of sorting.
Thank you, Joe. This is best explanation and explanation in python helps out a freshman in college.

[tombranson]

I find these exercises great... they help get your 'mind' in order and thinking like a computer. I am working on both Python and Ruby programming, so I have been coding these in both languages... it's interesting that I have to make fine adjustments between the 2 since it's not 1:1... they're close however... not as distinct as if I were translating Python to C+ or Java.
For example... I have been a little tricked up by Python's use of +1 or -1, which aren't necessarily needed in Ruby since it counts the exact number and we would place either two "periods" for including and three "periods" for up to and not including.
Fun stuff, always helps.

[rishabhkash]

Good explaination but, would be great if you could mention that code is not correct
Correction:
L = arr[first:middle+1]
R = arr[middle+1:last+1]

[DamienMurtagh-Galea]

Hi Joe. Recursion is my kryptonite. I just watched your video on recursion for the factorials, and it made complete sense. I am confused here, because at no stage is any value returned to the next function up. What am I missing?

[owninggreendragsdude]

Great explanation! Really helpful to see the code implemented as well. Subscribed.

[xy]

some merge sorts, will break down the left side into individual elements writing them in order to memory, before separating elements in the left side.

[orangetinyterrors]

I'd recommend doing some clean up... Using the sentinel value, for example, is just not necessary.

In other places it's somewhat odd to me to give or take 1. I think by reworking what "last" represents you can drop most of those corrections. That is, consider using the range [first, last) rather than [first, last] and just passing len(A) to merge_sort2 instead of len(A) - 1. (This will change the condition left < right to left < right - 1 but the recursive calls no longer have to use middle + 1, for the ranges [first, middle) and [middle, last).