Advanced Algorithms: Searching, Sorting and Path-Finding
Advanced algorithms for searching, sorting and path-finding, in A-level Computer Science, include merge sort, Dijkstra's algorithm and the A* algorithm. Merge sort is an efficient, recursive 'divide and conquer' sorting algorithm: it splits a list in half repeatedly until each part holds one (already sorted) item, then repeatedly merges pairs of sorted lists back together by always taking the smaller of the two lists' front values, giving it O(n log n) worst-case time complexity, better than a simple O(n^2) sort like bubble sort for large lists. Dijkstra's algorithm finds the shortest weighted path from a start vertex to every other vertex in a graph, by repeatedly visiting the closest not-yet-visited vertex and relaxing (updating) its neighbours' distances. The A* algorithm improves on Dijkstra's algorithm for finding a path to one specific target by adding a heuristic, an estimate of the remaining distance to the target, so it explores more directly towards the goal instead of expanding outward in every direction equally.
Before you start
Make sure you're comfortable with these topics first:
Method
- Recognise merge sort's two phases: divide (keep splitting the list in half until each sub-list has 0 or 1 items) and conquer (merge sorted sub-lists back together, doubling in size each time).
- When merging two already-sorted lists, compare only their current front (leftmost remaining) values, move the smaller one to the output, and repeat until one list is empty, then copy the rest of the other list across unchanged.
- Learn merge sort's Big O time complexity, O(n log n), and be able to explain why: log n levels of splitting, with O(n) work done merging at every level.
- For Dijkstra's algorithm, maintain a running table of the shortest known distance to every vertex (starting at 0 for the start vertex and infinity for every other vertex) and a set of visited vertices.
- At each step of Dijkstra's algorithm, visit the unvisited vertex with the smallest known distance, then relax every one of its edges: if the distance to the current vertex plus the edge's weight is less than a neighbour's currently known distance, update the neighbour's distance and record the current vertex as its predecessor.
- Stop Dijkstra's algorithm once the target vertex has been visited (or once every vertex has been visited, if every distance is needed), then reconstruct the shortest path by following the recorded predecessors backward from the target to the start.
- For A*, calculate f(n) = g(n) + h(n) for each candidate vertex n, where g(n) is the actual known distance from the start and h(n) is a heuristic estimate of the remaining distance to the target, and always expand the unvisited vertex with the smallest f(n) next.
- Check any heuristic used by A* is admissible (it never overestimates the true remaining distance), since this is what guarantees A* still finds the shortest path, while typically exploring fewer vertices than Dijkstra's algorithm.
Worked example
Trace merge sort on the list [8, 3, 5, 1, 9, 2], showing the divide and merge steps, and state the final sorted list.
- Split [8, 3, 5, 1, 9, 2] into two halves: left = [8, 3, 5], right = [1, 9, 2].
- Recursively sort the left half: split it into [8] and [3, 5], sort [3, 5] to [3, 5], then merge [8] with [3, 5] by always taking the smaller front value: 3, then 5, then 8, giving [3, 5, 8].
- Recursively sort the right half: split it into [1] and [9, 2], sort [9, 2] to [2, 9] (comparing 9 and 2, taking the smaller, 2, first), then merge [1] with [2, 9]: 1 is smaller than 2, so take 1 first, then take the rest of the already-sorted [2, 9], giving [1, 2, 9].
- Merge the two fully sorted halves, [3, 5, 8] and [1, 2, 9], by repeatedly comparing their front values and taking the smaller: compare 3 and 1, take 1; compare 3 and 2, take 2; compare 3 and 9, take 3; compare 5 and 9, take 5; compare 8 and 9, take 8; only 9 remains, so take it last.
- Final answer: the fully merged, sorted list is [1, 2, 3, 5, 8, 9].
Practice questions
Type your answer and press Check to be marked straight away, or reveal the answer and mark yourself.
Q1State the Big O time complexity of merge sort in the worst case.Show answer
Answer: O(n log n).
Q2The merge step of merge sort is given two already-sorted lists, [2, 6] and [4, 9]. State the single sorted list produced by merging them.Show answer
Answer: [2, 4, 6, 9] (compare 2 and 4, take 2; compare 6 and 4, take 4; compare 6 and 9, take 6; only 9 remains, take it last).
Q3State one advantage merge sort has over bubble sort for sorting a very large list.Show answer
Answer: Merge sort's worst-case time complexity, O(n log n), grows much more slowly than bubble sort's worst-case O(n^2) as the list size n increases, so merge sort completes in far fewer operations for a large list.
Q4Define what Dijkstra's algorithm calculates.Show answer
Answer: The shortest (lowest total weight) path, and its distance, from a single start vertex to every other vertex in a weighted graph.
Q5In Dijkstra's algorithm, explain what it means to 'relax' an edge from the current vertex to a neighbour.Show answer
Answer: Checking whether the distance to the current vertex plus the weight of the edge to the neighbour is smaller than the neighbour's currently known shortest distance, and updating the neighbour's distance (and its predecessor) if it is.
Q6State the vertex Dijkstra's algorithm always chooses to visit next, from those not yet visited.Show answer
Answer: The unvisited vertex with the smallest currently known distance from the start vertex.
Q7A* search uses f(n) = g(n) + h(n) to decide which vertex to explore next. For a vertex n, g(n) = 12 (the actual distance travelled so far to reach n) and its heuristic estimates the remaining distance to the target as h(n) = 8. State the value of f(n).Show answer
Answer: 20 (12 + 8).
Q8State one advantage A* search has over Dijkstra's algorithm when searching for a path to one single, specific target vertex.Show answer
Answer: A*'s heuristic guides it to explore vertices that seem closer to the target first, so it typically visits (expands) far fewer vertices than Dijkstra's algorithm, which explores outward from the start in every direction with no sense of where the target is.
Exam-style questions
Written in the style of a A Level Computer Science exam paper, with a full mark scheme.
Explain why merge sort's divide phase always takes O(log n) levels of splitting to reduce a list of n items down to individual items.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 2 available
A weighted, undirected graph has vertices A, B, C, D and E, with edges: A-B (weight 4), A-C (weight 1), B-C (weight 2), B-D (weight 1), B-E (weight 7), C-D (weight 5), D-E (weight 3). Use Dijkstra's algorithm, starting from vertex A, to find the shortest distance from A to every other vertex. Complete a table showing the current shortest known distance to each vertex after every vertex is visited (in the order it is visited), and state the shortest path (as a sequence of vertices) and its total weight from A to E.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 8 available
A satnav app needs to find the shortest driving route between the user's current location and a single chosen destination, on a road network with tens of thousands of junctions. A developer is deciding between implementing Dijkstra's algorithm and A* search. Evaluate which algorithm is more suitable for this specific use case.
Show mark scheme
Tick each line you got. Your score builds from the marks on the scheme.
Nothing ticked yet - 9 available
See real A Level Computer Science past-paper questions, with official mark schemes →
Free printable worksheet
Want more practice on paper? Download the advanced algorithms: searching, sorting and path-finding worksheet pack - 18 pages of exam-style questions with a full mark scheme. One email opens every download in this browser for 14 days - no account, no card. Print it for personal and classroom use.
Next topics
Not quite what you needed?
Tell us what is missing on advanced algorithms: searching, sorting and path-finding, or which topic to write up next. Every request is read, and we reply to every one.
Build a full practice pack.
This topic is one of hundreds in the library - pick the ones a student needs and generate a printable PDF in minutes.