Can We Merge Sort In Place?
Filter mode:
Topics
Media
(null topic)
🗪Chat Comment
🖮Programming🟉
🗩Speech
🎭
🏟
🔗
Link to: current timestamp
Credits
Host
Casey Muratori
Indexer
Matt Mascarenhas
?
?

Keyboard Navigation

Global Keys

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

Menu toggling

q Quotes r References f Filter y Link c Credits

In-Menu and Index Controls

a
w
s
d
h j k l
←
↑
↓
→

Esc Close menu / unfocus timestamp

Quotes and References Menus and Index

Enter Jump to timestamp

Quotes, References and Credits Menus

o Open URL (in new tab)

Filter Menu

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

Filter and Link Menus

z Toggle filter / linking mode

Credits Menu

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
3:57handmade_render_group.cpp: Introduce MergeSort
3:57handmade_render_group.cpp: Introduce MergeSort
3:57handmade_render_group.cpp: Introduce MergeSort
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
28:16handmade_render_group.cpp: Introduce Swap
28:16handmade_render_group.cpp: Introduce Swap
28:16handmade_render_group.cpp: Introduce Swap
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
31:56handmade_render_group.cpp: Label the steps
31:56handmade_render_group.cpp: Label the steps
31:56handmade_render_group.cpp: Label the steps
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:06handmade_render_group.cpp: Just set ReadHalf1 = InHalf1
1:06:06handmade_render_group.cpp: Just set ReadHalf1 = InHalf1
1:06:06handmade_render_group.cpp: Just set ReadHalf1 = InHalf1
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:09insofaras 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:09insofaras 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:09insofaras 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:08AlephAnt Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:08AlephAnt Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:08AlephAnt Off-topic, but I made a post about the 2^(2^n)) arguments for TSP on the forums, if you're interested
🗪
1:25:19robertogracia Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:19robertogracia Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:19robertogracia Could you post the bit of rotation math in the pre-stream in the Youtube Channel?
🗪
1:25:38fierydrake One of the variants in the Wikipedia article claims only one slot + O(1) extra pointers, required.
🗪
1:25:38fierydrake One of the variants in the Wikipedia article claims only one slot + O(1) extra pointers, required.
🗪
1:25:38fierydrake 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
🗩