Sorting & Selection Checkpoint

1. Quickselect recurses into:

Only the side that contains k Both sides Only the left side Only the right side

2. In merge-sort inversion counting, if left[i] > right[j], you add:

1 inversion All remaining elements in left All remaining elements in right 0 inversions

3. Average time complexity of quickselect with random pivots?

4. Quicksort worst-case time complexity is:

O(n^2) O(n log n) O(log n) O(n)

5. Define an inversion in an array.