27 March 2026
When “not in the mark scheme” doesn’t mean wrong – what Quicksort teaches us about accepting valid alternatives
A question that surfaces every revision season is this:
“If a student’s answer isn’t in the mark scheme, can they still get credit?”
Happily, the answer is yes.
Mark schemes guide examiners toward expected answers, but they’re not exhaustive. A response that demonstrates the required understanding, even if expressed differently, should still earn marks, and examiners are trained to recognise valid alternatives.
Few topics illustrate this better than the story of the Quicksort, and the many ways students might correctly perform it.
Remembering Tony Hoare, creator of Quicksort
It felt fitting to reflect on this, following the sad news that Professor Sir Charles Hoare (“Tony Hoare”) passed away peacefully on 5 March 2026 at the age of 92. Hoare is widely regarded as one of the greatest thinkers in the history of computing. His most famous contribution was the Quicksort, the algorithm that has sparked more A level debates and classroom disputes than possibly almost any other.
The origin story is wonderfully humble. In 1959, while studying machine translation at Moscow State University, Hoare needed a fast way to sort Russian words. Bubble sort wasn’t going to cut it. So, armed with paper and pencil, he devised Quicksort. Ironically, he couldn’t actually implement it, the language he was using, Mercury Autocode, was too limited.
When he returned to England and joined Elliott Brothers in 1960, one of his first tasks was to write a Shellsort. After completing it, he casually mentioned to his boss that he knew a faster method. His boss responded with a sixpence bet – one Hoare won when Quicksort outperformed all expectations.
So why don’t students’ Quicksorts match the mark scheme?
Quicksort isn’t a single algorithm. It’s a family of algorithms. Researchers and engineers have created hundreds of variants, each valid, each useful, each “Quicksort.”
This naturally leads to classroom friction:
- “That’s not how we learned it in Maths!”
- “But my teacher said the pivot never moves!”
- “This example is nothing like the mark scheme…”
The truth is: students aren’t wrong. Teachers aren’t wrong, and neither is the mark scheme! They’re often just using different, but valid variants. That’s exactly why rigidly expecting a single form of Quicksort can result in unfairly penalising correct answers.
What teachers should really look for with algorithms
Don’t advise students to memorise code blocks. Instead of matching specific code, teachers and students should look for the essential components that all Quicksort variants share:
- A pivot selection strategy
Common approaches include:
- First element
- Last element
- Middle element
- Random pivot
- Medianof3
- Medianof5
- Tukey’s ninther
- Adaptive schemes (e.g., introselect)
- A partitioning scheme
Popular methods include:
- Hoare partition – efficient, uses two indices
- Lomuto partition – conceptually simple, uses one index
- Bentley–McIlroy 3way – excellent for data with many duplicates
- Dualpivot – used in Java’s standard sort
- A recursive divide-and-conquer structure
Often supported by implementation choices such as:
- Tailrecursion elimination
- Cutoffs to insertion sort
- Memory layout optimisations
- Parallel variants
- Introsort hybrids
- Cacheoblivious versions
- A base case
The recursion stops when a sub list contains 0 or 1 elements.
- Combination of the results
When all partitions are sorted, the fully sorted list is formed.
Where the confusion really comes from
Most disagreement stems from the popularity of two different partitioning approaches: Hoare or Lomuto, and the fact that many teachers were taught one or the other.
To complicate things further a visualisation called the “Hungarian dancers” (thanks to a viral YouTube video) uses the first element as the pivot but allows it to move during partitioning meaning it’s not a pure Hoare partition, it’s a variant that is inefficient but can make it easier to visualise what the pivot is doing.
So, when a student’s working doesn’t match what’s in the mark scheme or what you’ve seen before, remember: it may still be a perfectly valid algorithm.
Want clear, classroom-friendly examples?
To support teachers CPD, we’ve included full walkthroughs of the Hoare, Lomuto, and the Hungarian variant with code in Python, C#, and Visual Basic in our book:
👉 https://www.amazon.co.uk/dp/B09NRBS8ND
Oh, and that documented meeting between Tony Hoare and Nico Lomuto we included? That’s just fiction! …but Tony did win the sixpence from his boss!
Check out the ‘At the chalk face’ podcast for more!
