Python: MergeSort algorithm explained 

Yeah, the code is absolutely wrong and not Pythonic.

You're a genius! I was struggling ever since time epoch! Jeez! Thank you!

Thanks bro I was struggling too

thanks! these changes work :)

You are correct. It works

Great to hear!

Definitely unique among all those tuts.

im on a mission, to learn basic algorithms 10 hrs before an exam

He knows we're all cramming and sleepy, legit wakes me up

Somewhat agree. Sentinel values are a widely used programming technique, not just invented by me. But list length would be better here.

Or Inf

@@oggiai , thanks for your video. I'm updating the merge function based on John's suggestion. def merge(A, first, mid, last): L = A[:mid] R = A[mid:] i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R[j]: A[k] = L[i] i += 1 else: A[k] = R[j] j += 1 k += 1 while i < len(L): A[k] = L[i] i += 1 k += 1 while j < len(R): A[k] = R[j] j += 1 k += 1

@@chenzhenmei8831 can you explain what is this part do? while i < len(L): A[k] = L[i] i += 1 k += 1 while j < len(R): A[k] = R[j] j += 1 k += 1

@@AhmadAfiqAzmi_xxnzonxx This part is to make sure that there is no leftover in the array(both left and right)

It’s a technique for detecting the end of the list called Sentry Value. There are other ways of doing it too.

@@oggiai But HOW is it detecting the end of the list. Thats what we are missing

@@mastermnd Actually it doesn't: the algorithm just doesn't go past that number since it's something like float("inf") and every other number is smaller than that; besides, if we consider how the algorithm is made (for list_idx in range(first, last+ 1)), that number will never be put in the ordered list because the for loop will end before reaching that point.

Yes, you are right. I need to update my code on github. Will do soon.

Is the code on github updated?

Same, it doesn't work without your tweak

@@MrPikulak thanks buddy. but will you please explain why it didn't work?

The values are returned when it reaches the base case. The function call stack keeps growing until the base case hits, then it works its way back down the call stack.

+owninggreendragsdude Thanks! Glad it was useful for you.

priya sodhi return it instead

do this arr= ["your list elements"] merge_sort(arr) print(arr) i think this may help you

+Tom Branson good insights.

Cool... for the folks having trouble... the programs work... I followed the videos and only for the quicksort did I have to resort to going to the GitHub link... since the final solution is not clear. I must say, the quicksort is one tough bastard to follow. I am going through it mentally, line-by-line... tough since you have to jump from function to function. These days newbies have all sort of created libraries and methods to do these things automatically almost, but I am sure that someone had to expend a lot of brain power to get this right the first time many moons ago... and sometimes magic sorting methods are just too magic... I like to lift the veil sometimes to learn more. I subscribed to your channel, Joe. Thanks

In your example, the L list would be split to call sort on [9, 5] and [2]. Then the returns from those sort calls would be in sorted order -- [5, 9], and [2] -- and they would be merged into [2, 5, 9]. You would never be merging L[ 9, 5, 2] and R[ 3, 4, 7] because L is not in sorted order, so it would continue breaking that down, then sorting as it merges them.

+Pratheek Bangera very good question. Actually it doesn't matter. When you split an odd-sized list in half, either the left half will be larger or the right half will be. But you'll get exactly the same result either way. MergeSort will continue splitting each list in half until it gets to a list of size 1, then it starts merging. It doesn't care whether the left side is 1 bigger or smaller than the right side for the intermediate lists.

+Joe James Thanks for the clarification Joe James. I will try this out now

yup. i got the same error

To find end of the list . there are many methods to find end of list

André Lino Never mind! My bad! I figured it out!

It’s an in-place sort, done on the original list, so there’s no return.

@@oggiai so does it mean that the sort is changing the order of the original array in real time? And if one was to write a merge sort with the return statement, would that create a new array instead of modifying the old one? It's mainly confusing for me because every pseudocode implemention of the merge sort always mentions the return statement and it also assigns each recursive code to a variable such as sorted_left = merge_sort(left_half) instead of only calling merge_sort(left_half).

@@davidandrejsin1259 Lists in python are mutable objects, so every action you do the list (even if it's inside a function) is done to the original list itself. With a return you'll have the function as a copy of the now-ordered list.

The method I presented is called "top-down" mergesort. There is also a "bottom-up" mergesort that is iterative rather than recursive. The both have the same performance.

Honestly, probably never. But there is value in learning how sorting algorithms work. You will have to write your own algorithms often, and learning a variety of basic sorting and graph traversal algos will help prepare you to do that. It’s a fundamental of computer science so you can understand more advanced programs. Data structures and algorithms are also the hottest topics for job interviews to test your skills. Believe it. I got a job offer from ETrade because I could explain how balanced trees work.

Because all companies out of their mind on the algorithms solving. So we need to deal with it

It’s just sentinel values to detect the end of the list. There are other ways of detecting the end of a list if you don’t like this method.

Joe James This method is cool but I don't know why it is necessary to know the end of the list and why the sentinel value can help system to detect the end

@@I-just-hold-white-paper-up I was wondering the same. It appears to me like the sentinel values are there to act as a visual clue for the sake of debugging. They can be manually changed to something like 99 or 999 and it still works. If I'm not mistaken, they act as padding to the lists so as to prevent a 'list index out of range' error. Also, the last iteration pops the remaining right item onto the final list. I see this question was asked 4 years ago, but maybe it'll help someone else...

That’s just a sentinel value to detect the end of each list.

+C-SPAM you're 100% right. You will rarely if ever need to write your own sorting algorithms. Nearly every language has built in sorting that is faster than any algorithm you write. CS students learn to write sorting algorithms mainly as a learning tool, not only to learn how sorting algorithms work but also to learn to use Big O to analyze and compare performance of different algorithms.

I understand the purpose behind videos like these after watching your video on hash tables, which was a great one by the way. Thank you for sharing these!

@@c-spam9581 sorting algorithms are typical interview questions to check your abstract thinking......this is maybe a very late response

Did you retype the code from the video, or did you download it from GitHub?

From github, my problem is I'm sorting a text file of random strings and I'm using merge sort to sort them and I get and error on the if L[i]

I see. You can use

Yes very true, thanks for the video.

Please try downloading and testing my code, then if you find bugs please try to provide relevant line numbers and I’ll check it out.

+KilljoyWithWhiskers 123 using 999999 is not a very elegant solution to be honest. I used it here because it's easy to follow. In practice I would use sys.maxsize or something like that.

Alright, thank you! We're GCSE Computer Science students using your videos to help us grasp the subject! :)

@@oggiai float("inf") maybe? So there's no need to import sys

+Raquel Melo you might try copying the code directly from my github site to make sure you don't have any typing or indention errors. If you get the same error then let me know what input list you're using and I'll check it out.

Did you retype the code from the video or download it from my GitHub site? I recommend getting the latest code from GitHub. If you copied and pasted any code you could have a mix of tabs and spaces for indents, so you should view hidden characters to check that. Also, this was written and tested in Python 3. If you are using Python 2 you may get errors. If none of these tips helps then tell me more about your error message and/or post your code.

@@oggiai Thanks for response and code is working now i had just created a small mistake while typing

If you want to see the process: def merge_sort(iterable: list): cont = 0 if len(iterable) % 2 == 0: new_iterable = [[i] if not isinstance(i, list) else i for i in iterable] else: new_iterable = [[i] if not isinstance(i, list) else i for i in iterable] new_iterable[-2].append(new_iterable[-1][0]) del new_iterable[-1] print(new_iterable) for i in range(0, len(new_iterable), 2): for j in range(len(new_iterable[cont + 1])): new_iterable[cont].sort() new_iterable[cont + 1].sort() new_iterable[cont].append(new_iterable[cont + 1][j]) cont += 1 del new_iterable[cont] print(new_iterable) if len(new_iterable) == 1: return new_iterable[0] return merge_sort(new_iterable)

use float('inf') instead

Jerry Chan could you explain it a little more?

@@bavidlynx3409 float("inf") creates an infinite (or at least a value that the compiler interpret as infinite), so every other number you compare with it is by default smaller.

Not meant to be production code, it's educational to help people learn how the algorithm works. Yes, Python 3 has sys.maxsize that may be more appropriate. But hopefully this video is significantly clearer and easier to follow than most other MergeSort videos you'll see so you can actually learn how mergesort works and how it can be implemented. Not to brag, but I don't see ANY other videos doing this.

for instance in one list, there might be all items lesser than other list items. So in this case, increment will happened in just one array and in the end it will go out of list's index range. So we have to limit j and k.

The way I wrote it works fine, and you can download my code from my github site if you want. Of course there are other ways to implement MergeSort. The reason your suggestion doesn't work with my implementation is that my implementation allows you to sort items 500 to 1000 of a 1M item list if you want. And with MergeSort you do need to make recursive calls on sublists of the main list, which I did by keeping 1 main list and passing as arguments the first and last index. Like I said, there are many other ways to do it. I encourage you to tinker with my code all you like.

Thanks

Es porque necessito traducirla en espanol? Or es demasiado complejo?

@@oggiai no, don't worry i'm just a beginner and theres some things i dont understand yet!! but your video is actually good, don't mind me!!!

Yes, that’s easier and works better, but it won’t help you much in a Google interview if they decide to drill you on algorithms.

@@oggiai you can avoid appending 99999 by checking i and j values

@@abadidibadou5476 Yes, but increasing if statements slows the algorithm.