sorting algorithms Flashcards
(19 cards)
What is the main idea behind Shellsort?
Use decreasing stride lengths to partially sort the array, ending with a final insertion sort.
How does Shellsort improve over insertion sort?
It allows distant elements to move earlier in the process, reducing the number of shifts needed later.
What determines Shellsort’s performance?
The gap (stride) sequence used.
What is the worst-case time complexity of Shellsort with Shell’s original gap sequence?
O(n²)
What is the worst-case time complexity of Shellsort with improved sequences?
O(n^{3/2})
Why is Shellsort more efficient than insertion sort?
Because it reduces disorder before the final insertion pass.
What does Shellsort preserve while sorting?
It preserves the permutation of the original array.
What is MergeSort’s core strategy?
Divide the array into halves, sort each recursively, then merge the results.
What does the merge step do in MergeSort?
It combines two sorted arrays into one sorted array by comparing and appending the smallest elements.
Why is the merge step critical to MergeSort?
Because the correctness of MergeSort depends on merging two sorted halves correctly.
What is the loop invariant in the Merge operation?
At each step, the merged result contains the smallest i elements from both arrays in sorted order.
How does MergeSort achieve O(n log n) time complexity?
Each level of recursion does O(n) work, and there are log n levels.
What is MergeSort’s recurrence relation?
T(n) = 2T(n/2) + n
What is the time complexity of MergeSort?
Θ(n log n)
Why is MergeSort better than quadratic algorithms for large n?
It handles large input sizes efficiently — much faster than O(n²).
How long would O(n²) take to sort 1 billion items?
Approximately 316 years (at 10⁸ ops/sec)
How long would MergeSort take for 1 billion items?
About 5 minutes (at 10⁸ ops/sec)
What type of algorithm is MergeSort?
A divide-and-conquer algorithm.
What are the benefits of using a loop invariant in MergeSort?
It helps prove that the merge step (and thus the full algorithm) maintains sorted order.
