# Question 1:

## Part (a)

| Answer | Mark | Guidance |
|--------|------|----------|
| The list is not in alphabetical order | B1 **(1)** | CAO – must explicitly mention list is not in alphabetical order; just stating "not in order" is B0, but give B1 bod for "not in A-Z order" |

## Part (b)

| Answer | Mark | Guidance |
|--------|------|----------|
| Quick sort demonstrated with pivot chosen (middle left or right) | M1 | Choosing first/last item as pivot is M0; first pass gives $<p, p, >p$ |
| First pass correct AND next pivot(s) chosen correctly for second pass | A1 | Second pass does not need to be correct |
| Second and third passes correct (follow through from first pass) | A1ft | No need to choose pivot for fourth pass |
| Sort complete, **named correctly** | A1 **(4)** | CSO – all previous marks must have been awarded; "sort complete" statement required or final sorted list shown |

## Part (c)

| Answer | Mark | Guidance |
|--------|------|----------|
| Pivot $1 = \left\lfloor\frac{1+9}{2}\right\rfloor = 5$, Kerry, reject $1-5$ | M1 | Mark pivot values only; allow restart from incorrect sorted list if correct (or implied) in (d) |
| Pivot $2 = \left\lfloor\frac{6+9}{2}\right\rfloor = 8$, Sylvester, reject $8-9$ | A1 | If K is not first pivot then M0 |
| Pivot $3 = \left\lfloor\frac{6+7}{2}\right\rfloor = 7$, Nikki, reject $7$ | A1 **(3)** | |
| Pivot $4 = 6$, Leslie – name found | | CSO – accept "found", "located", "stop" etc.; must be convinced Leslie has been located |

## Part (d)

| Answer | Mark | Guidance |
|--------|------|----------|
| e.g. $\log_2 727 = 9.505\ldots$ so $10$ or maximum number of items in each pass | M1 | |
| e.g. $727, 363, 181, 90, 45, 22, 11, 5, 2, 1$ so $10$ iterations | A1 **(2)** | |

**Total: 10 marks**

# Question 1 (Part d):

## Iterative approach (values at start of each iteration):
| Answer | Mark | Guidance |
|--------|------|----------|
| At least 727, 363, 181, 90, … or embedded in calculation e.g. $[727+1]/2 = 364$, $[363+1]/2 = 182$, $[181+1]/2 = 91$, $[90+1]/2 = …$ | M1 | |
| 727, 363, 181, 90, 45, 22, 11, 5, 2, 1 so 10 iterations | A1 | |

## Iterative approach (values at end of each iteration):
| Answer | Mark | Guidance |
|--------|------|----------|
| At least 363, 181, 90, … | M1 | |
| 363, 181, 90, 45, 22, 11, 5, 2, 1 so 10 iterations (so 9 iterations is A0) | A1 | |

## Other numerical arguments:
| Answer | Mark | Guidance |
|--------|------|----------|
| $2^n > 727$, taking logs of both sides and solving for $n$ (accept $2^n = 727$) OR stating $n = 9.5058…$ | M1 | Answer given correct to 1 decimal place |
| Above with $n = 10$ (no errors if calculation seen) | A1 | Allow recovery from equals |
| $2^n > 727$ then state $n = 10$ with no working unless $2^9$ also considered | M1 only | |
| $\log_2 727 = …$ | M1 | |
| $… = 9.505…$ and hence 10 | A1 | Answer given correctly to 1 dp |
| $\frac{727}{2^n}$ considered with $n=10$ is M1, showing explicitly that $n=10$ is first value giving less than 1; $\frac{727}{1024}$ or $0.7099…$ must be seen | M1, A1 | Not sufficient to just say $\frac{727}{2^{10}}$ is less than 1 |
| Halving 727 ten times gives value less than or equal to 1, showing $0.70996…$ correct to 1 d.p. | M1, A1 | Accept $= 1$ as halving/dividing by 2 context |
| Answer of 10 with no working | M0 | |

---