| Exam Board | OCR MEI |
|---|---|
| Module | D1 (Decision Mathematics 1) |
| Year | 2006 |
| Session | January |
| Marks | 8 |
| Paper | Download PDF ↗ |
| Mark scheme | Download PDF ↗ |
| Topic | Sorting Algorithms |
| Type | Algorithm Tracing |
| Difficulty | Easy -1.2 This is a straightforward algorithm tracing exercise requiring students to follow given instructions step-by-step and count operations. Parts (i)-(iii) involve mechanical execution with no problem-solving, while part (iv) requires only basic reasoning about best/worst cases for merging two sorted lists (max = x+y-1, min = min(x,y)). This is easier than average A-level content as it tests procedural following rather than mathematical insight. |
| Spec | 7.03d Order of algorithm: dominant term and scaling run-times7.03j Sorting: bubble sort and shuttle sort |
| Answer | Marks |
|---|---|
| (i) Merge sort algorithm traced through steps showing Lists 1, 2, 3 progressively merged to produce ordered final list | M1 sca; A1 to first step 3 inc.; A1 to second step 3; A1 rest |
| (ii) Merges ordered lists to give an ordered list | B1 |
| (iii) Number of passes: 7 | B1 |
| (iv) \(\text{Max} = x + y - 1\); \(\text{Min} = \min(x, y)\) | B1; B1 |
**(i)** Merge sort algorithm traced through steps showing Lists 1, 2, 3 progressively merged to produce ordered final list | M1 sca; A1 to first step 3 inc.; A1 to second step 3; A1 rest |
**(ii)** Merges ordered lists to give an ordered list | B1 |
**(iii)** Number of passes: 7 | B1 |
**(iv)** $\text{Max} = x + y - 1$; $\text{Min} = \min(x, y)$ | B1; B1 |
---(i) Complete the table in the insert showing the outcome of applying the algorithm to the following two lists:
$$\begin{array} { l r l l l l l }
\text { List 1: } & 2 , & 34 , & 35 , & 56 & & \\
\text { List 2: } & 13 , & 22 , & 34 , & 81 , & 90 , & 92
\end{array}$$
(ii) What does the algorithm achieve?\\
(iii) How many comparisons did you make in applying the algorithm?\\
(iv) If the number of elements in List 1 is $x$, and the number of elements in List 2 is $y$, what is the maximum number of comparisons that will have to be made in applying the algorithm, and what is the minimum number?
\hfill \mbox{\textit{OCR MEI D1 2006 Q2 [8]}}