16.06 - Searching and Sorting Algorithms

This page contains only GCSE content.

A searching algorithm is an algorithm to find the index of an item in a list.

There are two main searching algorithms: linear search and binary search.

Linear search checks each item in order from the start of the list until it finds the target item or reaches the end of the list.

Binary search takes a sorted list, and starts with the middle item. Then, if the target item is lower it discards the right half of the list, and if the target item is higher it discards the left half of the list. It keeps going until it finds the target item or discards every item.

A sorting algorithm is an algorithm to put the items of a list in order.

There are two main sorting algorithms: bubble sort and merge sort.

Bubble sort swaps pairs of numbers which are in the wrong order until the list is sorted. It requires up to n full passes for a list of length n, where in each pass all consecutive pairs are examined.

Merge sort repeatedly splits the list in half until each sub-list has only one item. Then, it sorts the items while putting the lists back together.

State the worst-case time complexities of each of the algorithms mentioned above.

Linear search: O(n), which means that doubling the length of the list doubles the maximum number of comparisons.
Binary search: O(log₂ n), which means that doubling the length of the list adds one to the maximum number of comparisons.

Bubble sort: O(n²), which means that doubling the length of the list quadruples the maximum number of comparisons.
Merge sort: O(n log₂ n), which means that doubling the length of the list roughly doubles the maximum number of comparisons.