Python Search & Sorting: Trace the Required Algorithms

Prerequisites: Python loops, lists, and index arithmetic; see the first two lessons in this module if needed. This lesson complements the analysis in [Algorithms](/notes/algorithms/divide-and-conquer-and-sorting).

Linear search checks each value and is correct on arbitrary input. Binary search repeatedly discards half the candidate interval, but it is valid only when the sequence is sorted under the same ordering used by the search.

Selection sort places the next minimum; bubble sort moves adjacent out-of-order values; insertion sort inserts the next item into an already sorted prefix. Mergesort recursively sorts halves and merges; quicksort partitions around a pivot. The syllabus names these algorithms, so the student must trace implementations and not only recognize their names.