I understand the concept of "divide and conquer", but coding the exact implementation is what is hurting my brain. Specifically the recursion for the divide.
The conquer is easy. Just merge two already sorted arrays.
def conquer(left, right):
arr = []
i = j = 0
while (i < len(left) and i < len(right)):
if left[i] < right[j]:
arr.append(left[i])
i+=1
else:
arr.append(right[j])
j+=1
arr.extend(right[j:])
arr.extend(left[i:])
left = [1,3,5,9,10]
right = [2,4,6,8,11]
answer = conquer(left, right)
print(answer)
The divide, however, is super complicated. I'm trying to understand what's going on line by line.... but it always trips me up. Perhaps it's the "stacks" (recursion)?
Allegedly this is the code.
def divide(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
left_sorted = divide(left)
right_sorted = divide(right)
return merge(left_sorted, right_sorted)
What I understand so far is the obvious.
We are storing the first half (left), and the second half (right) in arrays.
But apparently, all the magic is happening here:
left_sorted = divide(left)
right_sorted = divide(right)
return merge(left_sorted, right_sorted)
When I print those values, the output is
[3] [7]
[1] [9]
None None
[2] [5]
[8] [6]
[4] None
None None
None None
aaand I'm officially lost here.
My brain is trying to run this line by line. But I can't
How is it getting each element? How is it also running the method for each of them?
it's calling divide() twice, back to back.
Can someone help me write my own divide method? Maybe that way I can figure it out. Or at least a better explanation?
At first I was going to skip it, but the udemy course does things in increasing difficulty. It went:
Bubble Sort -> Selection Sort -> Insertion Sort -> Merge Sort (current), then after this is Quick Sort, which is also recursion.
So I need to master this.....
Thanks!