Can We Merge Sort In Place?

?

?# Keyboard Navigation

## Global Keys

[, < / ], > Jump to previous / next episode

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)## Menu toggling

q Quotes
r References
f Filter
y Link
c Credits
## In-Menu Movement

## Quotes and References Menus

Enter Jump to timecode

## 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)

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)

a

w

s

s

d

h
j
k
l

←

↑

↓

↓

→

X, ShiftSpace Toggle category and focus previous

v Invert topics / media as per focus

⏫

Previous: 'Examples of Sorting Algorithms'

⏫

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: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:28:02Wrap it up

🗩

1:28:02Wrap it up

🗩

1:28:02Wrap it up

🗩

⏬

Next: 'Implementing Radix Sort'

⏬