An array is an Abstract Data Type (ADT).

Mark scheme

Marking points from the official mark scheme (May/June 2025). The mark or mark type is shown in brackets.

1. [1] One mark for any two correct ADTs (Max 1)
2. • Binary tree
3. • Graph
4. • Linked list
5. • Queue
6. • Stack
7. [4] One mark for each marking point (Max 4)
8. MP1 Temporary assignment of the element being 'inserted' before inner loop
9. MP2 Appropriate inner loop
10. MP3 Check if current DataArray content is > Value
11. MP4 Moving data to adjacent element as required
12. MP5 Appropriate updating of Position variable
13. MP6 Re-insertion of the element outside the inner loop
14. Example algorithm: FOR Index ← 2 to 1000 Value ← DataArray[Index] Position ← Index - 1 IF DataArray[Position] > Value THEN WHILE Position >= 1 AND DataArray[Position] > Value DataArray[Position + 1] ← DataArray[Position] Position ← Position - 1 ENDWHILE DataArray[Position + 1] ← Value ENDIF NEXT Index
15. [2] One mark for each marking point
16. MP1 The performance of a sorting routine should improve if the data is already partially sorted // The performance of a sorting routine is likely to be worse if the data is completely out of order
17. MP2 The sort may take longer if the number of items to be sorted is larger // The sort may take less time if the number of items to be sorted is fewer.