Can We Merge Sort In Place?
?
?

Global Keys

W, K, P / S, J, N Jump to previous / next marker
t / T Toggle theatre / SUPERtheatre mode
V Revert filter to original state Y Select link (requires manual Ctrl-c)

q Quotes r References f Filter y Link c Credits

a
w
s
d
h j k l

o Open URL (in new tab)

x, Space Toggle category and focus next
X, ShiftSpace Toggle category and focus previous
v Invert topics / media as per focus

z Toggle filter / linking mode

Enter Open URL (in new tab)
1:12handmade_render_group.cpp: Note that the current SortEntries function is O(n^2), and introduce an early-out condition
1:12handmade_render_group.cpp: Note that the current SortEntries function is O(n^2), and introduce an early-out condition
1:12handmade_render_group.cpp: Note that the current SortEntries function is O(n^2), and introduce an early-out condition
3:08Introducing this condition changes the "expected running time" from O(n^2) to something less
3:08Introducing this condition changes the "expected running time" from O(n^2) to something less
3:08Introducing this condition changes the "expected running time" from O(n^2) to something less
8:58Blackboard: Can we Merge Sort in place?
8:58Blackboard: Can we Merge Sort in place?
8:58Blackboard: Can we Merge Sort in place?
14:22handmade_render_group.cpp: Introduce a validator for the sorting functions
14:22handmade_render_group.cpp: Introduce a validator for the sorting functions
14:22handmade_render_group.cpp: Introduce a validator for the sorting functions
15:30Debugger: Run the game and hit that assertion, before correcting the test
15:30Debugger: Run the game and hit that assertion, before correcting the test
15:30Debugger: Run the game and hit that assertion, before correcting the test
16:18handmade_render_group.cpp: Continue working on MergeSort, interleaving the tests
16:18handmade_render_group.cpp: Continue working on MergeSort, interleaving the tests
16:18handmade_render_group.cpp: Continue working on MergeSort, interleaving the tests
23:25Blackboard: Draw out the scenario
23:25Blackboard: Draw out the scenario
23:25Blackboard: Draw out the scenario
24:04handmade_render_group.cpp: Introduce Half0StackCount and write out all the cases explicitly
24:04handmade_render_group.cpp: Introduce Half0StackCount and write out all the cases explicitly
24:04handmade_render_group.cpp: Introduce Half0StackCount and write out all the cases explicitly
26:46Blackboard: Walk through the problem
26:46Blackboard: Walk through the problem
26:46Blackboard: Walk through the problem
30:08handmade_render_group.cpp: Step 1 - Find the first out-of-order pair
30:08handmade_render_group.cpp: Step 1 - Find the first out-of-order pair
30:08handmade_render_group.cpp: Step 1 - Find the first out-of-order pair
31:39Blackboard: The two phases of this merge sort algorithm
31:39Blackboard: The two phases of this merge sort algorithm
31:39Blackboard: The two phases of this merge sort algorithm
34:14Blackboard: Walk through the next phase
34:14Blackboard: Walk through the next phase
34:14Blackboard: Walk through the next phase
35:54handmade_render_group.cpp: Step 2 - Swap as many items as necessary
35:54handmade_render_group.cpp: Step 2 - Swap as many items as necessary
35:54handmade_render_group.cpp: Step 2 - Swap as many items as necessary
40:26Blackboard: Draw out the current situation
40:26Blackboard: Draw out the current situation
40:26Blackboard: Draw out the current situation
43:53handmade_render_group.cpp: Step 3 - Swap back as many swapped half0 items as necessary
43:53handmade_render_group.cpp: Step 3 - Swap back as many swapped half0 items as necessary
43:53handmade_render_group.cpp: Step 3 - Swap back as many swapped half0 items as necessary
51:37Blackboard: Rearranging the entries
51:37Blackboard: Rearranging the entries
51:37Blackboard: Rearranging the entries
55:20Blackboard: Consider how to swap the order of these blocks
55:20Blackboard: Consider how to swap the order of these blocks
55:20Blackboard: Consider how to swap the order of these blocks
59:22Blackboard: Consider the two cases
59:22Blackboard: Consider the two cases
59:22Blackboard: Consider the two cases
1:01:45Blackboard: Walk through what happens
1:01:45Blackboard: Walk through what happens
1:01:45Blackboard: Walk through what happens
1:06:48Blackboard: Construct a case and see what happens
1:06:48Blackboard: Construct a case and see what happens
1:06:48Blackboard: Construct a case and see what happens
1:10:43Blackboard: On the apparent need to store those back pointers
1:10:43Blackboard: On the apparent need to store those back pointers
1:10:43Blackboard: On the apparent need to store those back pointers
1:13:15handmade_render_group.cpp: Make MergeSort take some temporary storage and rewrite SortEntries to use that storage
1:13:15handmade_render_group.cpp: Make MergeSort take some temporary storage and rewrite SortEntries to use that storage
1:13:15handmade_render_group.cpp: Make MergeSort take some temporary storage and rewrite SortEntries to use that storage
1:19:29Debugger: Hit an assertion before fixing the test and seeing that the sort is correct
1:19:29Debugger: Hit an assertion before fixing the test and seeing that the sort is correct
1:19:29Debugger: Hit an assertion before fixing the test and seeing that the sort is correct
1:23:49Q&A
🗩
1:23:49Q&A
🗩
1:23:49Q&A
🗩
1:24:09 I didn't look this up so it might not work, but came up with: whenever an element from the upper half is chosen, put it in place in the lower half, shift the upper half down to fill the space that the chosen element used to take up, and store the non-chosen element from the lower half in the new space at the end of the upper half, setting the lower half's read pointer to that end bit. Thoughts?
🗪
1:24:09 I didn't look this up so it might not work, but came up with: whenever an element from the upper half is chosen, put it in place in the lower half, shift the upper half down to fill the space that the chosen element used to take up, and store the non-chosen element from the lower half in the new space at the end of the upper half, setting the lower half's read pointer to that end bit. Thoughts?
🗪
1:24:09 I didn't look this up so it might not work, but came up with: whenever an element from the upper half is chosen, put it in place in the lower half, shift the upper half down to fill the space that the chosen element used to take up, and store the non-chosen element from the lower half in the new space at the end of the upper half, setting the lower half's read pointer to that end bit. Thoughts?
🗪
1:25:08 Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:08 Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:08 Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:19 Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:19 Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:19 Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:38 One of the variants in the Wikipedia article claims only one slot + O(1) extra pointers, required.
🗪
1:25:38 One of the variants in the Wikipedia article claims only one slot + O(1) extra pointers, required.
🗪
1:25:38 One of the variants in the Wikipedia article claims only one slot + O(1) extra pointers, required.
🗪
1:28:02Wrap it up
🗩
1:28:02Wrap it up
🗩
1:28:02Wrap it up
🗩