What does one insertion step do?

• It slides the next value into its slot among the sorted ones
• It finds the smallest remaining value and swaps it to the front
• It deletes the largest value

What does one bubble sort pass do?

• It picks the minimum of the whole list at once
• It swaps out-of-order neighbours as it walks
• It splits the list in half

With an early exit flag, what does bubble sort do on a list that is already sorted?

• It still grinds through every pass
• It can finish in one pass with no swaps
• It runs slower than on reversed input

Why are both methods O(n squared)?

• Comparisons grow with n times n
• They each use exactly n comparisons
• They never compare anything

In the worst case, how many comparisons does insertion sort make on seven values?

Insertion sort runs in nearly linear time on nearly sorted input.

A student claims bubble sort always beats insertion sort because swapping looks faster. What is the error?

• Swapping decides nothing; on nearly sorted input insertion slots values in almost at once
• Bubble sort can never sort at all
• Insertion sort cannot handle small lists

Six values need 15 worst case comparisons. Roughly how many for twelve values?

• 30
• About 45
• About 66