Merge Sort

Question 1

Which sorting algorithm uses inversions to calculate the number of swaps needed to sort a list?

Answer 1

merge sort

Question 2

For the mechanism for merge sort, the list is _______ into two halves. Then, the ______ procedure is recursively applied to the ____ and _____ halves until each subarray contains a ______element. Finally, the two sorted subarrays are _________ back together.

Answer 2

divided, merge sort, left, right, single, merged

Question 3

What is the worst-case time complexity for merge sort? Why?

Answer 3

O(n log n) because the list dividing into halves is O(log n) and merging is O(n)

Question 4

What is the best-case time complexity for merge sort?

Answer 4

O(n log n)

Question 5

What is the space complexity of merge sort? Why?

Answer 5

O(n) due to temporary lists created in the merge step

Question 6

What prevents merge sort from performing O(n^2) despite its merge procedure?

Answer 6

Each element from on sorted half is only compared to the current element from the other sorted half

Question 7

For space complexity, merge sort uses _______ arrays.

Answer 7

temporary

Question 8

Does merge sort do any swaps during merging?

Answer 8

no!