Sorting Algorithms Exam Questions

• B Bubble sort (1)
• The only correct answer is B. The correct answer is bubble sort.
• A is not correct because a binary search is a search algorithm that halves a sorted list
• C is not correct because a linear search checks each item in turn
• D is not correct because a merge sort splits the list into sub-lists and merges them back together

• D Merge sort (1)
• The only correct answer is D. The correct answer is merge sort.
• A is not correct because a bubble sort sorts in place, swapping items in the original list
• B is not correct because a binary search is a search algorithm that halves a sorted list
• C is not correct because a linear search checks each item in turn

• A It makes fewer comparisons (1)
• The only correct answer is A. The correct answer is fewer comparisons.
• B is not correct because a merge sort still makes several passes as it splits and merges the list
• C is not correct because it is a bubble sort that moves the largest item into place on each pass
• D is not correct because a merge sort uses more memory as it creates additional sub-lists

Award one mark for any of the following up to a maximum of two marks:

• Each item is compared with the next/adjacent item (1)
• Items are swapped if they are in the wrong order (1)
• The item that is last in alphabetical order moves to the end of the list (1)
• An item can be swapped more than once during the pass (1)

Do not accept "the items are compared" without saying what they are compared with (the next/adjacent item), or "the list is sorted"/"items are put in order" with no reference to comparing or swapping.

Award one mark for any of the following up to a maximum of two marks:

• Divide/split the list into two halves/sub-lists (1)
• Continue dividing the sub-lists until each has one item (1)
• Merge/combine the sub-lists back into a single list (1)
• Merge the sub-lists in order / compare items when merging (1)

Do not accept "divide and conquer" on its own (repeats the stem).

Award one mark for any of the following up to a maximum of two marks:

• The number of comparisons made (1)
• The number of passes through the list/loop (1)
• The amount of memory used (1)

Allow the number of swaps made as an alternative to the number of comparisons, but do not award both.

Do not accept vague answers such as "how fast it is" / "it is quick" without a named measure.

Award up to two marks for a linked description such as:

• Each item is compared with the item next to it (1) so that they are swapped if they are in the wrong order (1)
• Items in the wrong order are swapped (1) so the largest item moves to the end of the list after one pass (1)
• Passes through the list are repeated (1) so that the sort stops when a pass makes no swaps (1)
• After each pass the last items are already in place (1) so fewer comparisons are made in the next pass (1)

Do not accept answers that only say the list is put in order or that repeat the question.

Do not accept descriptions of a merge sort, such as splitting the list in half and merging sub-lists.

Award up to two marks for a linked description such as:

• The list is split/divided into sub-lists (1) again and again until each sub-list holds a single item (1)
• Pairs of sub-lists are merged back together (1) by comparing the first item in each list and writing the smaller one to the new list (1)
• Merging the new sub-lists is repeated (1) until there is a single fully sorted list (1)

Award one mark for the divide stage and one mark for the merge stage, so the maximum for describing only the divide, or only the merge, is one mark.

Allow 'split into single items' on its own as the divide stage (1).

Do not award the merge mark for saying the sub-lists are merged back together unless the answer says how the items are put in order, e.g. by comparing items / writing the smaller one first.

Do not accept 'divide and conquer' on its own, with no description of the dividing or the merging.

Do not accept descriptions of a bubble sort, such as comparing and swapping items next to each other and then repeating the passes.

Award up to two marks for a linked description such as:

• Run both programs on the same set of test data (1) and count/record the number of comparisons each one makes (1)
• Run the programs on lists of different sizes (1) to see how the number of comparisons/passes changes as the list gets bigger (1)
• Time each program as it sorts the same test data (1) so the program that takes less time can be chosen (1)
• Use test data that is already in order (1) to see whether the number of passes through the loop changes (1)

Allow 'count the passes' as an alternative to 'count the comparisons'.

Do not accept 'see which one is faster/more efficient' with no reference to counting comparisons/passes or to measuring the time taken.

Do not accept descriptions of how either sort works, such as comparing and swapping items or splitting the list in half.

Award up to two marks for a linked explanation such as:

• Neighbouring/adjacent items are compared and swapped if they are in the wrong order (1) so the highest score is swapped one place to the right each time and keeps moving along the list (1)
• The larger item of a pair is swapped to the right (1) and is then compared with the next item, so the highest score works its way to the end of the list (1)
• The highest score is compared with the item to its right (1) and swapped with it, so it moves one place right on each comparison until it reaches the end (1)
• The list is worked through from left to right, comparing and swapping pairs (1) so the largest value is carried along to the end of the list (1)

For both marks, the expansion must follow/associate with the statement.

Allow one mark for a correct description of the comparison/swap of neighbouring items on its own, e.g. 'items next to each other are swapped if they are in the wrong order' (1), where it is not linked to the highest score reaching the end.

Do not accept 'it puts the list in order' / 'it sorts the scores' on its own, as this repeats the question without saying how.

Do not accept descriptions of a different sorting algorithm, e.g. finding the smallest score in the list and moving it to the front.

Award up to two marks for a linked explanation such as:

• The list is divided in half repeatedly (1) until each sub-list contains a single item (1)
• The list is split into two halves (1) and each half is split again until the sub-lists are one item long (1)
• Each sub-list is halved again and again (1) until it cannot be divided any further (1)
• Single-item sub-lists are produced (1) because the list is repeatedly divided into two (1)

For both marks, the expansion must follow/associate with the statement.

Do not accept descriptions of comparing items or merging sub-lists, as these happen in the merge stage, not the divide stage.

Award up to two marks for a linked explanation such as:

• The merge sort makes fewer comparisons (1) because the list is repeatedly halved, so each item is compared with far fewer other items (1)
• The bubble sort makes far more comparisons as the list gets longer (1) because every pass compares every neighbouring pair of items in the whole list (1)
• The merge sort does less work when combining the sub-lists (1) because each merge only compares the front item of two lists that are already sorted (1)
• The bubble sort needs many passes over the list (1) because each pass only moves one item into its final position, so passes repeat until no swaps are needed (1)

For both marks, the expansion must follow/associate with the statement.

Do not accept 'it is faster/quicker' or 'it is more efficient' on its own without a linked reason.

Do not accept 'the merge sort uses less memory', as a merge sort uses more memory than a bubble sort.

Indicative content

How bubble sort works

• Bubble sort compares each title with the one next to it and swaps them if they are in the wrong alphabetical order.
• Each pass moves the last unsorted title into its correct place at the end of the list, so the next pass can stop one title earlier and makes one fewer comparison than the pass before.
• Passes are repeated until a pass makes no swaps, which shows that the list is sorted.
• Sorting 40 titles could take up to 39 passes through the list.
• Bubble sort is an in-place sort, so the titles are rearranged inside the original list without creating a second list.

How merge sort works

• Merge sort splits the list in half again and again until each sub-list holds a single title.
• The sub-lists are then merged in pairs, repeatedly taking the title that comes first alphabetically from the front of each sub-list.
• Merging continues until one sorted list of 40 titles remains.
• Merge sort is a divide and conquer algorithm because it keeps dividing the list and then merges the sorted parts.

Number of comparisons

• In the worst case bubble sort makes 39 + 38 + ... + 1 = 780 comparisons for 40 titles, because adjacent titles are compared again on every pass and the number of comparisons falls by one on each pass.
• Merge sort makes far fewer comparisons, roughly 200 for 40 titles, because it needs about six rounds of splitting and merging and each round compares at most 40 titles; this figure is approximate, so accept any figure between about 150 and 250 that is given with a valid basis.
• Merge sort compares fewer titles because each merge only compares the titles at the front of the two sub-lists, not every pair.
• Fewer comparisons means the merge sort finishes sooner, but with only 40 titles both sorts finish in a fraction of a second.

Suitability

• Either sort is fit for purpose, because 40 titles is a small list and the program runs only once each day.
• Bubble sort is shorter and simpler to write and to check, which suits a small program like this one, so bubble sort can be recommended.
• Merge sort keeps extra sub-lists in memory, but this is not a problem on a desktop computer with plenty of RAM, so merge sort can also be recommended.
• Merge sort would be the better choice if the library later sorted a much larger catalogue, as its number of comparisons grows more slowly as the list gets longer.

Levels

• Level 0 (0 marks): No rewardable content.
• Level 1 (1–2 marks): Basic, independent points are made, showing elements of understanding of key concepts/principles of computer science. (AO1) The discussion will contain basic information with little linkage between points made or application to the context. (AO2)
• Level 2 (3–4 marks): Demonstrates adequate understanding of key concepts/principles of computer science. (AO1) The discussion shows some linkages and lines of reasoning with some structure and application to the context. (AO2)
• Level 3 (5–6 marks): Demonstrates comprehensive understanding of key concepts/principles of computer science to support the discussion being presented. (AO1) The discussion is well developed, with sustained lines of reasoning that are coherent and logically structured, and which clearly apply to the context. (AO2)

Level 3 answers must describe how both sorts work, compare their efficiency (number of comparisons, passes through the list or use of memory) and give a justified recommendation; either sort may be recommended, provided the reasoning is justified. Responses that only describe the two sorts, with no comparison of efficiency and no recommendation linked to the library's program, are limited to Level 2, and basic, unlinked descriptions of the two sorts are Level 1. Do not accept claims that merge sort uses less memory than bubble sort, or that a bubble sort divides the list in half.

Indicative content

Memory

• Bubble sort sorts the readings in place, swapping items inside the original list, so it needs only a small, fixed amount of extra memory however many readings there are. (accept: a constant amount of extra memory that does not grow with the number of readings)
• Merge sort is out-of-place, so new sub-lists are created at every split and extra memory is needed for them. (accept: merge sort needs an extra temporary list/array; merge sort needs extra memory that grows with the number of readings)
• The extra memory merge sort needs grows with the number of readings, so with up to 100 000 readings it could be more than the small device has.
• If the device runs out of memory, the program could crash or that night's readings might not be sorted.
• Bubble sort is therefore the safer sort for a device with limited memory.

Effect of the size of the list on time

• Bubble sort's number of comparisons grows roughly with the square of the number of readings, so sorting 100 000 readings would take a very long time.
• A bubble sort could need up to 99 999 passes over the list, whereas merge sort needs only about 17 rounds of splitting and merging. (accept: about log n rounds; accept merge sort makes roughly n log n comparisons)
• Merge sort's number of comparisons grows far more slowly as the list gets longer, so it copes far better with 100 000 readings.
• The program runs once a night, so there is a long time before the next day's readings are recorded, which may mean even a slow sort finishes in time.

Choice

• There is a trade-off, because the sort that is much faster on 100 000 readings is also the one that needs more memory.
• If the device has enough memory, merge sort should be chosen because it will sort the day's readings far more quickly.
• If memory is too tight, bubble sort may be the only sort that will run on the device, even though it will be slow.
• The developer could test both sorts with a full day's readings to see how long each takes and whether the device runs out of memory.

Levels

• Level 0 (0 marks): No rewardable content.
• Level 1 (1–2 marks): Basic, independent points are made, showing elements of understanding of key concepts/principles of computer science. (AO1) The discussion will contain basic information with little linkage between points made or application to the context. (AO2)
• Level 2 (3–4 marks): Demonstrates adequate understanding of key concepts/principles of computer science. (AO1) The discussion shows some linkages and lines of reasoning with some structure and application to the context. (AO2)
• Level 3 (5–6 marks): Demonstrates comprehensive understanding of key concepts/principles of computer science to support the discussion being presented. (AO1) The discussion is well developed, with sustained lines of reasoning that are coherent and logically structured, and which clearly apply to the context. (AO2)

Additional guidance

• Level 3 responses must consider both the memory each sort needs and the effect of the size of the list, and must reach a justified choice. A conditional choice, such as merge sort if the device has enough memory and bubble sort otherwise, is a justified choice and can reach Level 3.
• An answer that deals with only one of memory and the size of the list, even when it applies that point to the device, is limited to 3 marks (Level 2 lower).
• A recommendation that is not justified by the device's limited memory or by the time before the next day's readings is a basic point and will not, on its own, support Level 3.
• Do not credit the claim that merge sort uses less memory than bubble sort, because merge sort is out-of-place and needs extra memory for its sub-lists.
• Do not credit the claim that bubble sort is always quicker, or that merge sort is quicker, without considering how the number of readings affects the number of comparisons.