Unit 6: Efficient Sorting Algorithms & Analysis - Practice Quiz

1 Which sorting algorithm commonly has an average time complexity of ?

2 What does usually represent in the complexity ?

3 Which of the following is an efficient comparison-based sorting algorithm?

4 What is the main operation performed during the merge step of merge sort?

5 What is the base case in a recursive merge sort implementation?

6 How does recursive merge sort divide an array?

7 Which type of merge sort avoids recursive function calls?

8 What is the purpose of a pivot in quick sort?

9 What is the average time complexity of quick sort?

10 What can happen when quick sort repeatedly selects a poor pivot?

11 After partitioning around a pivot, where are smaller elements generally placed?

12 When sorting elements by frequency, what is counted first?

13 In frequency-based sorting, which value usually appears first when sorting by decreasing frequency?

14 What data structure is commonly used to store element frequencies?

15 What is the goal of finding the minimum length sorted sub-array?

16 If an array is already sorted, what is the minimum sub-array length that needs sorting?

17 Which order is commonly used when sorting strings lexicographically?

18 Which string comes first in lexicographic order?

19 In ASCII-based sorting, which character generally comes first?

20 What does case-insensitive sorting do?

21 A comparison-based sorting algorithm must sort every possible permutation of distinct elements. What lower bound applies to its worst-case number of comparisons?

22 Which algorithm guarantees worst-case time while also sorting an array in place using only auxiliary array storage?

23 A recursive merge sort is called on an array of elements. Assuming splitting continues until sub-arrays have one element, how many merge levels are required?

24 In bottom-up iterative merge sort, the initial run size is . What sequence of run sizes is processed when sorting an array of elements?

25 During the merge step, two records have equal keys, with the left record appearing earlier in the original array. Which comparison preserves merge sort's stability?

26 Lomuto partition is applied to [4, 2, 7, 3, 1, 5], using the last element as the pivot. What array and pivot index result after one partition?

27 Quick sort always selects the first element as pivot. Which input is most likely to produce its worst-case running time?

28 An optimized quick sort recursively processes the smaller partition and handles the larger partition iteratively. What is the main benefit of this strategy?

29 Sort [4, 6, 2, 4, 3, 2, 4, 3, 3] by decreasing frequency. If frequencies tie, preserve the order in which values first appeared. What is the result?

30 Elements are sorted by decreasing frequency, with smaller values first when frequencies tie. What is the sorted form of [5, 2, 5, 3, 2, 4]?

31 For the array [1, 3, 5, 4, 2, 6, 7], what is the minimum length of a contiguous sub-array that must be sorted to make the entire array sorted?

32 What should an algorithm return as the minimum sub-array length when the input array is already sorted in nondecreasing order?

33 After locating the first inversion from each end, an algorithm finds the minimum and maximum values inside the candidate sub-array. Why may its boundaries need to be expanded?

34 Using case-sensitive ASCII lexicographic order, what is the sorted order of ['Zebra', 'apple', 'Banana', 'apricot']?

35 Strings are sorted first by increasing length and then lexicographically when lengths tie. What is the result for ['pear', 'fig', 'apple', 'kiwi', 'plum']?

36 Sort lowercase and uppercase letters separately while preserving which positions contain lowercase and uppercase letters. What does defRTSersUXI become?

37 A stable case-insensitive sort is applied to ['Bob', 'alice', 'ALICE', 'bob']. What is the result?

38 How many distinct value pairs in [1, 5, 3, 4, 2, 2] have an absolute difference of ?

39 For [1, 1, 1, 2, 2, 3], how many distinct value pairs have an absolute difference of ?

40 A sorted array may contain duplicates. In a two-pointer algorithm that counts distinct pairs with difference , what should happen after a valid pair is found?

41 Why can no deterministic comparison-based sorting algorithm guarantee substantially fewer than comparisons for every permutation of distinct elements?

42 Two independently sorted arrays contain and distinct elements. What is the tight worst-case number of comparisons needed to merge them into one sorted array?

43 A bottom-up merge sort processes an array of length using run widths . It invokes the merge procedure only when a right run exists. How many width passes and merge invocations occur?

44 During merge sort, the left and right halves are already sorted. If the next right-half value is smaller than the next left-half value at index , how should an inversion-counting implementation update the count?

45 A recursive merge sort alternates the roles of source and destination arrays at successive recursion levels. What is the main benefit of this technique when implemented correctly?

46 Suppose every Quick Sort pivot splits a subarray of size into parts of sizes approximately and . Which asymptotic bounds describe the total running time and the longest recursion path?

47 For randomized Quick Sort on distinct elements, where every pivot is chosen uniformly, what is the expected number of key comparisons?

48 An array contains identical keys. How does randomized Quick Sort behave when using a correct three-way partition into keys less than, equal to, and greater than the pivot?

49 Sort [4, 6, 2, 4, 3, 2, 4, 6, 2] by decreasing frequency, breaking equal-frequency ties by first occurrence in the original array. What is the result?

50 An array of length has only distinct values. Frequencies are stored in a hash map, distinct values are sorted by (-frequency, value), and each value is then emitted according to its frequency. What is the expected time complexity?

51 For the array [1, 3, 5, 4, 2, 6, 7], which smallest zero-based inclusive interval must be sorted so that the entire array becomes nondecreasing?

52 After finding an initial unsorted interval $[l,r]`, let $m$ and $M$ be its minimum and maximum. Which expansion rule gives the minimum interval for a nondecreasing final array?

53 A function must return the length of the smallest subarray whose sorting makes the full array nondecreasing. What should it return for [1, 2, 2, 3, 5]?

54 A comparison sort orders strings, each of length at most , using ordinary lexicographic comparison without caching longest common prefixes. What is its worst-case character-comparison complexity?

55 Using code-point lexicographic order, where uppercase A precedes lowercase a and a proper prefix precedes the longer string, how are ["a", "aa", "", "ab", "A"] sorted?

56 Uppercase letters must be sorted among the original uppercase positions, and lowercase letters among the original lowercase positions. Applying this rule to bAcDaeC produces which string?

57 Which set of conditions is sufficient to verify an output of case-specific string sorting?

58 For [1, 1, 1, 2, 2, 3, 4, 4], how many distinct unordered value pairs satisfy an absolute difference of ?

59 For [1, 1, 3, 3, 5, 5, 7], how many distinct unordered value pairs have absolute difference ?

60 A sorted, deduplicated array is scanned with indices to count pairs satisfying for . Which pointer-update rule is correct?