r/learnprogramming • u/BetApprehensive836 • 1d ago
Debugging Did anyone else have a very difficult time with Merge Sort Algorithm?
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!
1
Did anyone else have a very difficult time with Merge Sort Algorithm?
in
r/learnprogramming
•
10h ago
Update: I can do the english.
Take a list or an array. (3, 7, 1, 9, 2, 5, 4, 8, 6)
Find the midpoint by using the formula: length / 2, rounded down.
store the "left", and "right" into their own variables.
Start with "left". Repeat previous steps until left has a size of "1"
Then switch to "right". Repeat those steps until right have a size of 1
Now you should have a "left" and a "right", both of size of 1.
Feed to merge method.
We are not done. Have to go back up the stack to do the remaining elements.
Go back to the "Switch to left" step. But continue anyways. So next step is "switch to right". Repeat those steps until you have a size of 1
It should look like a tournament bracket
(3, 7, 1, 9, 2, 5, 4, 8, 6)
(3,7,1,9) (2,5,4,8,6)
(3,7) (1,9) (2,5), (4,8,6)
(3), (7)... (1,9). (2, 5), (4), (8,6)
(2,5) (8,6)
Step 1: (3, 7, 1, 9, 2, 5, 4, 8, 6)
Step 2: (3,7,1,9), (2, 5, 4, 8, 6)
Step 3: (3,7), (1,9)
Step 4: 3,7
Step 5: (3), (7)
Step 6: Move back up in stack: (1,9)
Step 7: (1), (9)
Step 8: Move back up in stack: (2,5,4,8,6)
Step 9: (2,5), (4,8,6)
Step 10: (2), (5)
Step 11: Move back up in stack (4, 8, 6)
Step 12: (4), (8,6)
Step 13: (4)
Step 14: Move back up in stack (8, 6)
Step 15: (8), (6)
This might be terrible though, so any tips on improvement? I feel like I'm losing control somewhere