What is the space complexity of a top-down merge sort on a linked list due to recursion?

• A. O(1)
• B. O(n)
• C. O(n log n)
• D. O(log n)

Answer: (D)

When sorting a linked list with a top-down merge sort, the space used beyond the list itself comes from the recursion stack. Each recursive call adds a frame to the call stack, and the maximum number of concurrent frames equals the depth of the recursion. Since each split halves the list size, the depth is about log2(n). That means the extra space due to recursion grows logarithmically with n, i.e., O(log n). The merging step can be done by re-linking existing nodes in place, so it doesn’t require linear extra memory. Therefore, the space complexity caused by recursion is O(log n).