Had some trouble making this work in Python 3 at first. line 30, in merge_sort left, right = merge_sort(a[:(len(a)/2)]), merge_sort(a[(len(a)/2):]) Managed to fix this with a workaround: lgt = int(len(a) / 2) left, right = merge_sort(a[:lgt]), merge_sort(a[lgt:])
You can also set a midpoint variable as below and use it midpoint = int(len(a)/2) # to cater for a being odd left, right = merge_sort(a[:midpoint]), merge_sort(a[midpoint:])
Or just use "//" left, right = merge_sort(a[:(len(a)//2)]), merge_sort(a[(len(a)//2):]) rather than....... left, right = merge_sort(a[:(len(a)/2)]), merge_sort(a[(len(a)/2):])
First I couldn't believe how fast you're typing but then realised that you speeded up.I was going crazy mate:)))) Thanks for the good explanation by the way.
I had to do a bit of work around but I got it. if you use len(arr)/2 in python 3, you'll get an index error so I did this instead def merge_sort(arr): if len(arr)
I needed to use floor division for indexing in the the recursive function calls on left and right. Why didn't you? In the case of odd numbers, I get an error.
I'm just trying to understand this (learning MergeSort for the first time and your video is great). But I'm having trouble understanding this. Does your merge function assume that the left and right lists you are passing to it are already sorted? Because if your left list and unsorted, and your right list is unsorted - does this still work? I guess I'll test it and see.
Mmm ok i just tested and it does not work. You also mentioned in the video that the lists you pass to your merge function are already sorted, so it doesn't work with unsorted lists. However, I don't see any pre-sort going on in your merge_sort function. It looks like the only thing you are doing is splitting up the input list into 2 halves, and then you call your merge function to merge them. Those 2 halves are most likely 2 unsorted lists, because they were generated by your create_array function, which is a randomized list. So based on that... I'm failing to understand how the 2 halves are sorted so that when passed to your merge function it works. It must mean that those 2 halves become sorted somehow within your "3 lines" of code within the merge_sort function - but i just can't see it, or I'm missing something here arghh
Ah ok I see the secret is in your left, right = merge_sort(a....) line. This function is calling itself within itself. I'll need to visualize this for a bit to understand it mmm.
Happy to see you understand it a bit more, the merge function will actually never (as long as everything is working) be passed two unsorted arrays. The first time merge is called it is passed two arrays of length 1, then 2, and so on, but every time the two inputs are always sorted. If you have any questions or need anything clarified let me know.
Thanks. I was looking to learn BFS next and wanted to watch one of your videos on it (because I like your videos) - but it doesn't seem like you've done one on BFS?
I keep getting this error left,right = merge_sort(a[:len(a)/2]), merge_sort(a[len(a)/2:]) TypeError: slice indices must be integers or None or have an __index__ method
You can also set a midpoint variable as below and use it midpoint = int(len(a)/2) # to cater for a being odd left, right = merge_sort(a[:midpoint]), merge_sort(a[midpoint:])
8:01 - "because bubble, insertion and selection sort all suffer from exponential time complexity in the worst case..." Do you mean *quadratic time complexity* in the worst case? AFAIK those algorithms only need to traverse pair of nested loops, so their time complexity should be quadratic at worst: O(n^2).
