# Question 1:

## Part (a)
| Answer/Working | Marks | Guidance |
|---|---|---|
| Quick sort performed with pivot chosen and two sublists one $<p$ one $>p$ | M1 | If choosing 1 pivot per iteration only M1 only |
| First pass correct: M L J H **K** T R I → J H I K M L T R (pivot K highlighted) | A1 | First pass correct and next pivots chosen correctly/consistently |
| Second pass correct | A1ft | Second pass correct, next pivots correctly/consistently chosen |
| Third pass correct | A1ft | Third pass correctly/consistently chosen |
| Sort complete | A1cso | All correct, cso |

## Part (b)
| Answer/Working | Marks | Guidance |
|---|---|---|
| $1^{\text{st}}$ choice $\left\lceil\frac{1+8}{2}\right\rceil \rightarrow 5$ Lauren, reject right | M1 A1 | Binary search, choosing pivot, rejecting half list. If using unsorted list, M0. Accept choice of K for M1 only |
| $2^{\text{nd}}$ choice $\left\lceil\frac{1+4}{2}\right\rceil \rightarrow 3$ John, reject right | A1ft | First pass correct, condone 'sticky' pivot here, bod. Second pass correct, pivot rejected |
| $3^{\text{rd}}$ choice $\left\lceil\frac{1+2}{2}\right\rceil \rightarrow 2$ Imogen, reject right | | |
| $4^{\text{th}}$ choice 1 Hannah, reject. List now empty so Hugo not in list | A1 | cso |

---