Mergesort works by splitting a list of n numbers in half, then sorting each half recursively, and finally merging the two halves. Which of the following list implementations would allow Mergesort to work in \Theta(n \log n) time?

(1) A singly linked list
(2) A doubly linked list
(3) An array

(1), (2), and (3)
  • None of them"
  • (1) only
  • (2) only
  • (3) only
  • (1) and (2) only
  • (1) and (3) only
  • (2) and (3) only

We have an implementation that works on arrays.

It is also easy to do this on linked lists.

It works fine on both singly and doubly lined lists.