4.3.5.2 Merge sort Quiz: AQA Computer Science, Unit 3

The 20 questions

1. What is the time complexity of merge sort?

   • O(n log n)
   • O(log n)
   • O(n log n squared)
   • O(n^2)

2. Merge sort is an example of which approach to problem solving?

   • Dynamic programming only
   • Greedy
   • Brute force
   • Divide and conquer

3. Which algorithmic strategy does merge sort use?

   • Backtracking
   • Divide and conquer
   • Dynamic programming
   • Greedy approach

4. What is combined during the merge step of merge sort?

   • Adjacent elements only
   • Two unsorted lists
   • Random list items
   • Two sorted sublists

5. What is the average time complexity of merge sort?

   • O(n^2)
   • O(n)
   • O(n log n)
   • O(log n)

6. What is the auxiliary space complexity of merge sort?

   • O(n)
   • O(1)
   • O(log n)
   • O(n^2)

7. Merge two sorted lists [1, 4, 7] and [2, 3, 8]. What is the result?

   • [1, 2, 3, 4, 8, 7]
   • [1, 2, 3, 4, 7, 8]
   • [2, 3, 1, 4, 7, 8]
   • [1, 4, 7, 2, 3, 8]

8. How many times can an 8-item list be halved before single items remain?

   • 8
   • 4
   • 2
   • 3

9. What is the sorted output of merge sort applied to [38, 27, 43, 3]?

   • [3, 38, 27, 43]
   • [38, 27, 3, 43]
   • [27, 3, 38, 43]
   • [3, 27, 38, 43]

10. Merging the sorted lists [2, 6, 9] and [1, 5] with the standard merge step, what is the first item output?

    • 2
    • 1
    • 9
    • 5

11. What is the maximum number of comparisons needed to merge two sorted lists of lengths 4 and 4?

    • 8
    • 16
    • 4
    • 7

12. How many halving levels does merge sort use for 1024 items?

    • 1024
    • 512
    • 10
    • 5

13. Roughly how many operations does merge sort need for n = 1024 items?

    • 1048576
    • 10240
    • 1024
    • 523776

14. Compared with bubble sort on the same 1024 items, merge sort needs roughly how many times fewer operations?

    • About 2 times
    • About 10 times
    • About 50 times
    • About 1000 times

15. How does a stable merge sort resolve ties during merging?

    • Discard one item
    • Take left item
    • Take right item
    • Swap both items

16. What is the recursion depth of merge sort on n items?

    • n levels
    • Exactly two levels
    • n squared levels
    • About log2 n levels

17. Roughly how many comparisons does merge sort need to sort 1000 items?

    • About 1,000,000
    • About 1,000
    • About 10,000
    • About 100,000

18. What is the worst-case time complexity of the merge sort algorithm?

    • O(1)
    • O(n)
    • O(n²)
    • O(n log n)

19. A merge sort sorts 16 items. How many merge operations occur in total?

    • 16
    • 8
    • 15
    • 4

20. What is the best-case time complexity of standard merge sort?

    • O(n^2)
    • O(1)
    • O(n)
    • O(n log n)

Related quizzes

• Breadth-first and depth-first search Quiz · 4.3.1.1 · 20 questions
• Pre-order, post-order and in-order traversal Quiz · 4.3.2.1 · 20 questions
• Infix to Reverse Polish notation Quiz · 4.3.3.1 · 20 questions
• Linear and binary search Quiz · 4.3.4.1 · 20 questions
• Binary tree search Quiz · 4.3.4.3 · 20 questions
• Bubble sort Quiz · 4.3.5.1 · 20 questions
• Dijkstra's shortest path algorithm Quiz · 4.3.6.1 · 20 questions
• Data types Quiz · 4.1.1.1 · 20 questions
• Entity relationship modelling Quiz · 4.10.1.1 · 20 questions
• Big Data Quiz · 4.11.1.1 · 20 questions