Merge Sort Flashcards

All 4 cards in this deck

What are the main steps of a merge sort?
e.g. sort 4, 1, 3, 2

1. Split the list in half repeatedly until each list holds one item: 4 | 1 | 3 | 2.
2. Merge pairs of lists, comparing values so each merged list is in order: 1, 4 and 2, 3.
3. Keep merging until one list remains: 1, 2, 3, 4.

Which sorting algorithm splits the data into individual items before recombining them in order?

Merge sort.

Why is a merge sort efficient?

Very short lists are trivial to sort, and combining two lists that are already in order takes few comparisons.

In a merge sort, how are two ordered sub-lists merged into one?

Compare the first remaining item of each sub-list, move the smaller one into the new list, and repeat until every item has been moved.