Sorting Algorithms II

Merge sort uses which of the following techniques to implement sorting?

• Backtracking

• Greedy algorithm

• Divide and conquer

• Dynamic programming

What is the best case time complexity of merge sort?

• O(1)

• O(log n)

• O(n)

• O(n log n)

What is the worst case time complexity of merge sort?

• O(n log n)

• O(𝑛 2 )

• O(𝑛 2 log 𝑛)

• O(n log 𝑛 2 )

What is the auxiliary space complexity of merge sort?

• O(1)

• O(log n)

• O(n)

• O(n log n)

A stable sorting algorithm

• Does not crash

• Does not run out of memory

• Does not change the sequence of appearance of elements

• Does not exist

An adaptive sorting algorithm

• Adapts to new inputs

• Takes advantage of already sorted elements

• Takes inputs which are already sorted

• None of the above

Which of the following is not an in-place sorting algorithm?

• Merge sort

• Quick sort

• Bubble sort

• Insertion sort

Choose the incorrect statement about merge sort from the following:

• It is a comparison based sort

• It is an adaptive algorithm

• It is not an in-place algorithm

• It is a stable algorithm

Choose the correct code for a merge sort.

• 
• 
• 
• 

Quick sort follows the divide-and-conquer strategy.

• True

• False