Sorting Algorithms (Module 5) PART 3 Flashcards
1
Q
What are the mechanisms of merge sort? (3 steps)
A
1) divide the list into two halves
2) apply merge sort procedure for left and right halves until each subarray has a single element
3) two sorted arrays are merged back together and sorted
2
Q
What is the best-case time complexity for performance analysis?
A
O(n log n)
3
Q
What is the worst-case time complexity for merge sort?
A
O(n log n)
4
Q
What is the space complexity for merge sort?
A
O(n)
5
Q
What prevents merge sort from preforming O(n^2)?
A
each element from a sorted half is only compared to the current element of the sorted half
