PRACTICE • LEARN • GROW
Sorting MCQs
Solve topic-wise placement questions and improve your skills.
Sorting Progress
0 of 39 completed
0%
Topic Track
You are viewing MCQs in preview mode. Log in to select options, submit answers, and track your progress.
Log In to Answer
1
Which of the following sorting algorithms is NOT stable in its standard textbook implementation?
A.
Quick Sort
B.
Merge Sort
C.
Insertion Sort
D.
Bubble Sort
Explanation & Key
Correct Answer:
2
What is the theoretical lower bound on time complexity for any comparison-based sorting algorithm on N elements?
A.
Omega(N)
B.
Omega(N log N)
C.
Omega(log N)
D.
Omega(N^2)
Explanation & Key
Correct Answer:
3
Which sorting algorithm is most efficient for an array where every element is at most k positions away from its sorted position?
A.
Quick Sort with random pivot
B.
Selection Sort
C.
Min-Heap Sort using a heap of size (k + 1)
D.
Merge Sort
Explanation & Key
Correct Answer:
4
What is the worst-case space complexity of standard Merge Sort on an array of size N?
A.
O(1)
B.
O(log N)
C.
O(N log N)
D.
O(N)
Explanation & Key
Correct Answer:
5
What is the worst-case time complexity of QuickSort and when does it typically occur in standard Lomuto partitioning?
A.
O(N^2), when the array is already sorted and the last element is chosen as pivot
B.
O(N log N), when all elements are distinct
C.
O(N), when elements are in reverse sorted order
D.
O(N^3), when recursion depth exceeds 100
Explanation & Key
Correct Answer:
6
What is the time complexity of building a Binary Heap of N elements using the bottom-up `buildHeap` (heapify) procedure?
A.
O(N log N)
B.
O(N)
C.
O(log N)
D.
O(N^2)
Explanation & Key
Correct Answer:
7
Which sorting algorithm runs in linear O(N + K) time where K is the range of input values?
A.
Heap Sort
B.
Quick Sort
C.
Counting Sort
D.
Shell Sort
Explanation & Key
Correct Answer:
8
Why is Radix Sort capable of sorting N integers with d digits in O(d * (N + b)) time without violating the Omega(N log N) lower bound?
A.
Because it uses multi-threading
B.
Because d is always larger than log N
C.
Because it uses balanced binary search trees
D.
Because it is a non-comparison based sorting algorithm
Explanation & Key
Correct Answer:
9
What is the worst-case time complexity of Insertion Sort and when does its best-case O(N) occur?
A.
Worst-case O(N^2); Best-case O(N) when the array is already sorted
B.
Worst-case O(N log N); Best-case when reverse sorted
C.
Worst-case O(N^3); Best-case O(1) when empty
D.
Worst-case O(N); Best-case O(log N)
Explanation & Key
Correct Answer:
10
What makes TimSort (the default sorting algorithm in Python and Java Objects) particularly powerful for real-world data?
A.
It uses GPU parallel processing
B.
It combines Merge Sort and Insertion Sort to exploit already sorted runs in real-world data
C.
It runs in O(log N) time for all arrays
D.
It sorts data without using any memory
Explanation & Key
Correct Answer:
11
What is the auxiliary space complexity of standard In-Place Heap Sort?
A.
O(N)
B.
O(log N)
C.
O(1)
D.
O(N log N)
Explanation & Key
Correct Answer:
12
How many total comparisons does Selection Sort make on an array of size N?
A.
O(N) in best case, O(N^2) in worst case
B.
O(N log N) comparisons
C.
Zero comparisons because it uses hashing
D.
N * (N - 1) / 2 comparisons in all cases (best, average, worst)
Explanation & Key
Correct Answer:
13
Which sorting algorithm has the minimum number of write/swap operations (O(N) writes), making it optimal when writes to memory are costly?
A.
Cycle Sort
B.
Merge Sort
C.
Bubble Sort
D.
Quick Sort
Explanation & Key
Correct Answer:
14
What is the time complexity of QuickSort when 3-way partitioning (Dutch National Flag algorithm) is applied on an array with all identical elements?
A.
O(N^2)
B.
O(N)
C.
O(N log N)
D.
O(N!)
Explanation & Key
Correct Answer:
15
What is the average number of inversions in a randomly permuted array of size N?
A.
N / 2
B.
N * log N
C.
N * (N - 1) / 4
D.
N^2 / 2
Explanation & Key
Correct Answer:
16
Which algorithm is best suited for sorting a linked list in O(N log N) time and O(1) auxiliary space?
A.
Quick Sort
B.
Heap Sort
C.
Selection Sort
D.
Merge Sort
Explanation & Key
Correct Answer:
17
What is Shell Sort's core optimization over standard Insertion Sort?
A.
It sorts items far apart using gaps and progressively reduces the gap size
B.
It uses a hash table to group identical keys
C.
It partitions elements around a median of three pivot
D.
It divides elements into binary trees
Explanation & Key
Correct Answer:
18
What is the recurrence relation for the time complexity of standard Merge Sort?
A.
T(N) = T(N-1) + O(N)
B.
T(N) = 2T(N/2) + O(N)
C.
T(N) = 2T(N/2) + O(1)
D.
T(N) = T(N/2) + O(N)
Explanation & Key
Correct Answer:
19
Why is standard QuickSort preferred over MergeSort for sorting arrays in internal memory in C++ `std::sort`?
A.
QuickSort is stable whereas MergeSort is not
B.
QuickSort has a guaranteed O(N) worst case
C.
QuickSort has better cache locality and requires O(log N) auxiliary stack rather than O(N) heap memory
D.
QuickSort requires no comparisons
Explanation & Key
Correct Answer:
20
What is Introsort (used in C++ `std::sort`)?
A.
A combination of Radix Sort and Bubble Sort
B.
An interactive sorting algorithm for graphical displays
C.
A neural network sorting procedure
D.
A hybrid of QuickSort, HeapSort, and InsertionSort
Explanation & Key
Correct Answer:
21
What is the stability of Heap Sort?
A.
Unstable, because heap operations reorder duplicate keys based on tree levels and swaps
B.
Always stable
C.
Stable only if min-heap is used
D.
Stable only if input has distinct elements
Explanation & Key
Correct Answer:
22
Which of the following sorting algorithms is adaptive (runs faster when input is partially sorted)?
A.
Selection Sort
B.
Insertion Sort
C.
Heap Sort
D.
Standard Merge Sort
Explanation & Key
Correct Answer:
23
What is the space complexity of recursion in randomized QuickSort in the average case?
A.
O(N)
B.
O(1)
C.
O(log N)
D.
O(N log N)
Explanation & Key
Correct Answer:
24
What is the time complexity of Bucket Sort when input numbers are uniformly distributed over [0, 1)?
A.
O(N^2)
B.
O(N log N)
C.
O(1)
D.
O(N) on average
Explanation & Key
Correct Answer:
25
Which pass of Bubble Sort can detect if the array is already sorted and terminate early in O(N) time?
A.
By tracking a boolean `swapped` flag in the first pass
B.
By checking only the first and last elements
C.
Bubble Sort cannot detect pre-sortedness
D.
By reversing the array first
Explanation & Key
Correct Answer:
26
What is the theoretical lower bound on time complexity for any comparison-based sorting algorithm in the worst case?
A.
O(n)
B.
O(n log n)
C.
O(n^2)
D.
O(log n)
Explanation & Key
Correct Answer:
27
How does Counting Sort break the Omega(n log n) comparison-sort barrier to achieve O(n + k) time?
A.
By using quantum computing instructions
B.
By not comparing elements against each other; instead using integer keys directly as array indices to count frequencies
C.
By multithreading comparisons across cores
D.
By assuming the array is already sorted
Explanation & Key
Correct Answer:
28
Why does Quick Sort with Median-of-Three pivot selection prevent worst-case O(n^2) degradation on sorted or reverse-sorted inputs?
A.
It selects the median of arr[lo], arr[mid], and arr[hi], avoiding extreme (smallest/largest) pivot choices
B.
It converts Quick Sort into Merge Sort
C.
It allocates an auxiliary array of size 3
D.
It sorts the entire array in 3 steps
Explanation & Key
Correct Answer:
29
What is the auxiliary space complexity of Merge Sort on an array of size n?
A.
O(1)
B.
O(n) for the temporary merge buffer
C.
O(n^2)
D.
O(log n)
Explanation & Key
Correct Answer:
30
Which sorting algorithm is used by default in Python (`sort()`) and Java (`Arrays.sort()` for objects)?
A.
Quick Sort
B.
Tim Sort (a hybrid of Merge Sort and Insertion Sort)
C.
Heap Sort
D.
Bubble Sort
Explanation & Key
Correct Answer:
31
What is the worst-case time complexity of Quick Sort, and under what condition does it occur with standard Lomuto partition?
A.
O(n log n) when all elements are distinct
B.
O(n^2) when the chosen pivot is consistently the smallest or largest element (e.g. already sorted array with last element as pivot)
C.
O(n^3)
D.
O(n)
Explanation & Key
Correct Answer:
32
How can Radix Sort sort n 32-bit integers in O(n) linear time?
A.
By sorting digit-by-digit or byte-by-byte using Counting Sort across 4 passes of 8 bits each (base 256)
B.
By dividing numbers by 32
C.
By treating integers as floating point values
D.
By hashing each integer into a hash set
Explanation & Key
Correct Answer:
33
Why is Insertion Sort faster than Merge Sort or Quick Sort on small arrays (e.g. n <= 16)?
A.
Because it has lower constant factors, zero recursion overhead, and excellent cache locality
B.
Because its asymptotic complexity is O(log n)
C.
Because it uses binary search internally
D.
Because modern compilers optimize out the loops
Explanation & Key
Correct Answer:
34
What is an Inversion in an array?
A.
A pair of indices (i, j) such that i < j and arr[i] > arr[j]
B.
A negative number in the array
C.
An element equal to 0
D.
An element at the wrong memory address
Explanation & Key
Correct Answer:
35
How can the total number of inversions in an array be counted in O(n log n) time?
A.
Nested loops
B.
During the merge step of Merge Sort: when an element from right half is chosen before left half, remaining elements in left half form inversions
C.
Using Quick Sort partition
D.
Using Binary Search on every element
Explanation & Key
Correct Answer:
36
Which of the following sorting algorithms is in-place AND stable?
A.
Merge Sort
B.
Quick Sort
C.
Insertion Sort
D.
Heap Sort
Explanation & Key
Correct Answer:
37
What is the Best Case time complexity of Bubble Sort with an `isSwapped` flag optimization on an already sorted array?
A.
O(n^2)
B.
O(n)
C.
O(log n)
D.
O(n log n)
Explanation & Key
Correct Answer:
38
How does Hoare's partition scheme compare to Lomuto's partition scheme in Quick Sort?
A.
Hoare's scheme uses two pointers converging from both ends and performs on average 3 times fewer swaps than Lomuto's scheme
B.
Hoare's scheme is stable while Lomuto is not
C.
Lomuto's scheme is faster on all datasets
D.
Hoare's scheme requires O(n) extra memory
Explanation & Key
Correct Answer:
39
What is Bucket Sort and when does it achieve O(n) average time complexity?
A.
When inputs are uniformly distributed across a range [0, 1), partitioning elements into buckets and sorting each with Insertion Sort
B.
When input values are powers of 2
C.
When the array is already reverse-sorted
D.
When the array fits in CPU registers
Explanation & Key
Correct Answer:
Question Palette
Answered
Current
Not Attempted
Wrong
