# Question 1:

## Part (a)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Quick sort demonstrated with pivots selected and first pass giving $<p$, $p$, $>p$ | M1 | Quick sort – pivots selected and first pass gives $<p$, $p$, $>p$. **If only choosing one pivot per iteration M1 only.** |
| First pass correct, next two pivots chosen correctly for second pass | A1 | First pass correct, next two pivots chosen correctly for second pass |
| Second and third passes correct (follow through from first pass and choice of pivots) and next pivot(s) chosen consistently for fourth pass | A1ft | Follow through from their first pass and choice of pivots |
| CSO and 'sort complete' | A1 | Could be shown **either** by a 'stop' statement **or** final list rewritten **or** using each item as a pivot |

## Part (b)

| Answer/Working | Marks | Guidance |
|---|---|---|
| Pivot $1 = \left[\frac{1+9}{2}\right] = 5$, McCANN, reject 1–5 | M1 | Choosing middle right pivot (choosing middle left is M0) + discarding/retaining half the list. M1 **only** for an 'incorrect' list – allow 1 error or 1 omission or 1 extra |
| Pivot $2 = \left[\frac{6+9}{2}\right] = 8$, QUAGLIA, reject 8–9 | A1 | First and second passes correct i.e. $5^{th}$ and $8^{th}$ items for a correct list **and** second half rejected (no sticky pivots) |
| Pivot $3 = \left[\frac{6+7}{2}\right] = 7$, PATEL. $P =$ PATEL, name found (so 3 iterations) | A1 | CSO. Third pass correct i.e. $7^{th}$ item for a correct list + "found". Accept 'found', 'located', 'stop' etc. but not just the letter. Number of iterations does **not** need to be stated explicitly |

## Part (c)

| Answer/Working | Marks | Guidance |
|---|---|---|
| $\log_2 641 = 9.324$, so 10, or maximum number of items in each pass: $641, 320, 160, 80, 40, 20, 10, 5, 2, 1$ | M1 | For at least $641, 320, 160, 80, \ldots$ or embedded in calculation e.g. $\left[\frac{641+1}{2}\right] = 321$, $\left[\frac{320+1}{2}\right] = 161$, etc. |
| So 10 iterations | A1 | If considering maximum values at end of each iteration: $320, 160, 80, \ldots, 1$ so 9 iterations is A0 |

# Question 1 (Numerical Arguments - Binary Search/Iterations):

| Answer/Working | Mark | Guidance |
|---|---|---|
| $2^n > 641$, taking logs: $n > \log_2 641$ | M1 | Either take logs of both sides and solve for $n$, or state $n = 9.32...$ (accept $2^n = 641$) |
| $n = 9.32...$ (1 dp) hence $n = 10$ | A1 | Above with $n=10$, no errors if calculation seen (allow recovery from equals) |
| $\log_2 641 = \cdots = 9.32...$ giving $n=10$ | M1 | Alternative: $\log_2 641$ stated |
| $\frac{641}{2^{10}} = \frac{641}{1024} = 0.625...$ shown explicitly | M1, A1 | Must show $n=10$ is first value giving result less than 1; stating $\frac{641}{1024}$ less than 1 insufficient alone |
| Answer of 10 with no working | M0 | — |

**Quick Sort Table (middle left pivot):**

| Pass | Pivots |
|---|---|
| M S Q C **E** P B F O E | E |
| **C** B E M S **Q** P F O | C, Q |
| **B** C E M **P** F O **Q** S | (B), P, (S) |
| B C E M **F** O P Q S | F |
| B C E F **M** O P Q S | M |
| B C E F **M** O P Q S | (O) |

Sort complete.

---