| Bin 1: 35  17  7 | M1 A1 A1 | (3) |
|---|---|---|
| Bin 2: 10  28  15 | | |
| Bin 3: 23  20 | | |
| Bin 4: 41 | | |
| Bin 5: 29 | | |

**Part (b):** Quick sort with pivot choices and correct ordering

| e.g. middle right | M1 | |
| 35  17  10    7   28  23  41  15   20  29 | M1 | |
| | A1 | |
| 35  28  41  29  23  17  10  7   15  20 | A1ft | |
| 41  35  28  29  23  17  20  15  10  7 | A1 | (4) |

Pivot(s): 23, 41, 7; 23, 41, 7; 41, 7; 29, 20, (10); Sort complete

| Bin 1: 41  17 | M1 A1 A1 | (3) |
|---|---|---|
| Bin 2: 35  23 | | |
| Bin 3: 29  28 | | |
| Bin 4: 20  15  10  7 | | |

| $8 < x < 12, \quad y > x, \quad (y > 8)$ | B3, 2, 1, 0 | (3) |

**Notes for Question 4:**

**PLEASE NOTE NO MISREADS IN THIS QUESTION – MARK ACCORDING TO THE SCHEME AND THE SPECIAL CASES IN PART (b) and the guidance for the M mark in (c)**

- **a1M1:** First four items placed correctly (the values in bold) and at least seven values placed in bins. Condone cumulative totals for M1 only – if one of the bold values appears in more than one bin then M0
- **a1A1:** First eight items placed correctly (the underlined and bold values) – if one of the underlined values appears in two different bins then this is A0
- **a2A1:** CSO (correct solution only – so no additional/repeated values)
- **b1M1:** Quick sort, pivot, p, chosen (must be choosing middle left or right – choosing first/last item as the pivot is M0). After the first pass the list must read (values greater than the pivot), pivot, (values less than the pivot). If only choosing one pivot per iteration then M1 only
- **b1A1:** First two passes correct
- **b2Ift:** Third pass correct (follow through from their second pass and choice of pivots for the third pass (these pivots for the third pass must be either middle left or middle right)
- **b3A1:** CSO (correct solution only – all previous marks in this part must have been awarded) including a 'sort complete' - this could be shown by the final list being re-written or 'sorted' statement or each item being used as a pivot (which would therefore mean that the final list would have been written twice)

**middle left examples:**
- 35  17  10    7   28  23  41  15   20  29 → 28
- 35  41  29  28  17  10    7   23  15  20 → 41, 7
- 41  35  29  28  23  17  10  15  7 → 35, 23
- 41  35  29  28  23  17  10  15  7
- 41  35  29  28  20  17  15  10  7 → Sort complete
- 41  35  29  28  23  17  20  15  10  7
- 41  35  29  28  23  17  15  10  7

**SC for (b):** If using an incorrect list from the start of (b) with only one error (an error is either one missing number, one extra number, two numbers transposed or one incorrect number) then the most they can score is M1A0A1ftA0

**Sorting list into ascending order in (b):**
- If the candidate sorts the list into ascending order and reverses the list in this part then this can score full marks in (b)
- If the list is not reversed in (b) then remove the last two A marks earned in (b). If the list is reversed at the start of (c) but not in (b) then still remove the last two A marks earned in (b). If the list is in ascending order in (b) award no marks for first-fit increasing in (c). If the candidate says that the list needs reversing in (b) but does not actually show the reversed list in (b) then remove the last A mark earned

- **c1M1:** Must be using a list that is in strictly descending order. If it is clear that their list is not in descending order then M0. First five items placed correctly (the bold values) and at least eight values placed in bins – condone cumulative totals for M1 only – if one of the bold values appears in more than one bin then M0. If it is clear that their list is not correct (41 35 29 28 23 20 17 15 10 7) then M1 only and for this M mark allow them to be using their final list from (b) which can contain one error and in this case an error is either one missing number or one extra number or one incorrect number (e.g. 24 for 23) but their list must be in descending order.
- **c1A1:** First seven items placed correctly (the underlined and bold values) – if one of the underlined values appears in two different bins then this is A0
- **c2A1:** CSO (so no additional/repeated values)
- **d1B1:** $x > 8$
- **d2B1:** $x < 12$

If B0 B0 then award B1  B0 for $8 ≤ x ≤ 12$ (oe)

- **d3B1:** $x < y$ but not $y > 8$ only

For full marks in (d) no additional incorrect constraints, for example, if B1B1B1 initially awarded but an additional incorrect constraint seen (e.g. $y > 15$) then award B1B1B0 but do not penalise any additional incorrect constraints unless all three other correct constraints seen

---