Sorting algorithms study guide

1. Identify the algorithmic mechanism

Start by deciding which operation controls the trace. Bubble sort works through adjacent comparisons and swaps. For each relevant pair, determine whether the order is correct. If it is not correct, exchange the two items and continue the pass. A good trace records the list after each swap, because the changing order provides evidence that the algorithm has been applied correctly.

Merge sort must be traced differently. Show the list being divided into smaller lists, then show the sorted lists being merged. The merge stage compares the available items from the lists being combined and places the next item into the output in sorted order. Keep the division stage separate from the merging stage so that the Divide and Conquer approach is clear.

2. Connect the trace to complexity

The specified time complexity for bubble sort is O(n²). In an explanation, link this to the repeated work of making comparisons through the list and making further passes. This is why bubble sort is identified as particularly inefficient in terms of time.

The specified time complexity for merge sort is O(n log n). Link this to its two-part structure: the input is divided into smaller parts, and the resulting parts are merged in a controlled way. The important comparison is that merge sort has the lower stated growth rate, O(n log n) rather than O(n²).

3. Exam application method

For a trace question, first copy the starting list accurately. Then label or describe each pass for bubble sort, or each division and merge for merge sort. After every operation, check that the displayed list follows from the previous one. For a complexity question, name the algorithm, state its exact Big O expression, and justify the expression using its mechanism. Do not give only a complexity symbol when the question asks for analysis.

4. Self-check

Ask yourself: Can I explain what bubble sort compares? Can I show where a swap occurs? Can I divide a list and then merge the parts in the correct order? Can I state that bubble sort is O(n²) and merge sort is O(n log n) without reversing them? Finally, check that an answer distinguishes bubble sort's repeated adjacent comparison process from merge sort's Divide and Conquer process.