Merge Sort

Question 1

Merge sort is a stable sorting algorithm, which means it maintains the ___________________ in the input array

Answer 1

relative order of equal elements

Question 2

What is the BEST case time complexity of Merge Sort, and when does it occur?

Answer 2

O(n log n), When the array is already sorted or nearly sorted.

Question 3

What is the AVERAGE case time complexity of Merge Sort, and when does it occur?

Answer 3

O(n log n), When the array is randomly ordered.

Question 4

What is the WORST case time complexity of Merge Sort, and when does it occur?

Answer 4

O(n log n), When the array is sorted in reverse order.

Question 5

Why is merge sort suitable for parallel processing?

Answer 5

It independently merges subarrays

Question 6

Merge sort is not an in-place sorting algorithm. What is the disadvantage of this?

Answer 6

It requires additional memory to store the sorted data.

Question 7

Which is faster: merge sort or quick sort? Why?

Answer 7

Merge Sort is Slower than QuickSort in general as QuickSort is more cache friendly because it works in-place.

Question 8

What sort of data structure is merge sort especially good at sorting?

Answer 8

Linked lists

Question 9

______.sort in Java uses QuickSort while ______.sort uses MergeSort.

Answer 9

Arrays.sort; Collections.sort