Suppose we are sorting an array of nine integers using quicksort, and we have just finished the first partitioning with the array looking like this: 4 2 3 8 9 11 13 12 10 Which statement is correct?

A) Either 8 or 9 could be the pivot

B) 8 could be the pivot, but 9 cannot

C) 9 could be the pivot, but 8 cannot

D) Neither 8 nor 9 can be the pivots

Which of the following sorting algorithms in its typical implementation gives best performance when applied on an array which is sorted or almost sorted (maximum 1 or two elements are misplaced).

A) Insertion sort

B) Selection Sort

C) Bubble Sort

D) All of the above

What does the below array look like after 2 passes/iterations of Selection Sort (when sorting in increasing order)?

A) 6, 5, 1, 2, 0

B) 0, 5, 1, 2, 6

C) 0, 1, 2, 5, 6

D) 0, 1, 6, 2, 5

E) 0, 1, 5, 2, 6 1

What is the time complexity of the merge phase in mergesort ?

A) O(n)

B) O(n log n)

C) O(log n)

D) O(log (log n))