Sorting Algorithms MCQs for Gate Exam -

Sorting Algorithms— GATE-Level MCQs

Q1. Which of the following sorting algorithms has the best average-case time complexity?
A) Insertion Sort
B) Bubble Sort
C) Merge Sort
D) Selection Sort

✅ Answer: C) Merge Sort
Solution:
Average time complexity:

Insertion/Bubble/Selection: O(n²)
Merge Sort: O(n log n)
Hence, Merge Sort is the most efficient on average.

Q2. If Quick Sort always selects the largest element as the pivot, the worst-case time complexity for sorting an array of 120 elements is:
A) O(120 log 120)
B) O(120²)
C) O(log 120)
D) O(120)

✅ Answer: B) O(120²)
Solution:
If the pivot is always the largest (or smallest), one partition is empty each time → recursion depth = n → O(n²) worst-case.

Q3. Which sorting algorithm is stable and non-adaptive?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Selection Sort

✅ Answer: A) Merge Sort
Solution:
Merge Sort preserves relative order (stable) but does not adapt to nearly sorted data → non-adaptive.

Q4. Consider an array with elements [42, 15, 23, 8, 4]. After one pass of Bubble Sort, the array becomes:
A) [15, 23, 8, 4, 42]
B) [15, 42, 23, 8, 4]
C) [8, 4, 15, 23, 42]
D) [42, 23, 15, 8, 4]

✅ Answer: A) [15, 23, 8, 4, 42]
Solution:
Bubble Sort compares adjacent pairs and pushes the largest element (42) to the end in first pass.

Q5. Which sorting algorithm requires O(1) auxiliary space?
A) Merge Sort
B) Heap Sort
C) Radix Sort
D) Counting Sort

✅ Answer: B) Heap Sort
Solution:
Heap Sort is in-place → O(1) space. Merge and Counting/ Radix Sorts need additional space.

Q6. The number of comparisons in Selection Sort for an array of size n = 6 is:
A) 15
B) 30
C) 10
D) 20

✅ Answer: A) 15
Solution:
Comparisons = (n(n−1))/2 = 6×5/2 = 15.

Q7. In Quick Sort, the partitioning step for an array of size 9 takes O(9). The number of such steps in the worst case is:
A) 9
B) log₉
C) 1
D) 9²

✅ Answer: A) 9
Solution:
Each step partitions 1 element → total steps = n = 9. Hence overall O(n²).

Q8. Which sorting algorithm is most efficient for sorting linked lists?
A) Insertion Sort
B) Merge Sort
C) Quick Sort
D) Heap Sort

✅ Answer: B) Merge Sort
Solution:
Linked lists are efficiently split and merged; Merge Sort avoids random access and works in O(n log n).

Q9. The minimum number of swaps required to sort the array [5, 2, 3, 1, 4] using Selection Sort is:
A) 4
B) 2
C) 3
D) 5

✅ Answer: C) 3
Solution:
Selection Sort swaps only when minimum changes:
→ 1,2,3,5,4, 1,2,3,4,5, one extra at last → 3 swaps total.

Q10. Counting Sort cannot be applied when:
A) Range of data is small
B) Data are integers
C) Data are negative
D) Data are repeated

✅ Answer: C) Data are negative
Solution:
Counting Sort needs array index ≥ 0; negative keys require offset mapping.

Q11. The best case time complexity of Insertion Sort is O(n). When does it occur?
A) When array is sorted in descending order
B) When array is random
C) When array is sorted in ascending order
D) Never

✅ Answer: C) When array is sorted in ascending order
Solution:
No shifting needed → best case O(n).

Q12. Which sorting algorithm can be efficiently implemented using a queue?
A) Heap Sort
B) Merge Sort
C) Radix Sort
D) Quick Sort

✅ Answer: C) Radix Sort
Solution:
Radix Sort uses queues (or buckets) for digit-wise sorting.

Q13. A sorting algorithm that compares elements only and has the lower bound of Ω(n log n) is:
A) Counting Sort
B) Bucket Sort
C) Merge Sort
D) Radix Sort

✅ Answer: C) Merge Sort
Solution:
Comparison-based sorting cannot go below Ω(n log n).

Q14. For n = 100 elements, Heap Sort performs approximately how many comparisons?
A) 500
B) 100 log₂100
C) 1000
D) 10

✅ Answer: B) 100 log₂100
Solution:
Heap Sort ≈ O(n log n) comparisons → 100 × log₂100 ≈ 100 × 6.64 ≈ 664 comparisons.

Q15. If we apply Merge Sort on an already sorted array of size n = 8, the number of comparisons made is:
A) 8
B) 15
C) 7
D) 20

✅ Answer: B) 15
Solution:
Merge Sort does fixed pattern of comparisons, independent of data order → (n log₂n − n + 1) ≈ 8×3 − 7 = 17 ~15.

Q16. Which algorithm sorts in-place and is not stable?
A) Bubble Sort
B) Insertion Sort
C) Heap Sort
D) Merge Sort

✅ Answer: C) Heap Sort
Solution:
Heap Sort rearranges elements arbitrarily → not stable, but in-place.

Q17. The time complexity of Bucket Sort is O(n + k). What is k?
A) Number of buckets
B) Number of comparisons
C) Number of elements
D) Depth of recursion

✅ Answer: A) Number of buckets
Solution:
k = number of buckets; total complexity O(n + k).

Q18. Which of the following sorting algorithms is adaptive?
A) Selection Sort
B) Insertion Sort
C) Merge Sort
D) Heap Sort

✅ Answer: B) Insertion Sort
Solution:
Insertion Sort reduces time when input is nearly sorted → adaptive.

Q19. Suppose an algorithm takes 64 comparisons to sort 8 elements. What is the approximate time complexity?
A) O(n²)
B) O(n log n)
C) O(n³)
D) O(n)

✅ Answer: A) O(n²)
Solution:
n = 8 → n² = 64. Matches quadratic complexity.

Q20. Which sorting method is not comparison-based?
A) Merge Sort
B) Counting Sort
C) Quick Sort
D) Heap Sort

✅ Answer: B) Counting Sort
Solution:
Counting Sort uses index arithmetic, not comparisons.

💠 100 Tricky MCQs on Sorting Algorithm(Data Structures) for GATE

Q1. Which of the following sorting algorithms has the best average-case time complexity?
A) Insertion Sort
B) Bubble Sort
C) Merge Sort
D) Selection Sort
✅ Answer: C
Explanation: Merge Sort gives O(n log n) on average, while others give O(n²).

Q2. If Quick Sort always selects the largest element as the pivot, its worst-case complexity for n = 1000 elements is:
A) O(1000 log 1000)
B) O(1000²)
C) O(log 1000)
D) O(1000)
✅ Answer: B
Explanation: Always selecting the largest or smallest element gives unbalanced partitions → O(n²).

Q3. Which sorting algorithm is stable and non-adaptive?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Selection Sort
✅ Answer: A
Explanation: Merge Sort maintains relative order (stable) but does not adapt to input.

Q4. Bubble Sort performs how many swaps in the worst case for n = 10?
A) 10
B) 45
C) 100
D) 55
✅ Answer: B
Explanation: Total swaps = n(n−1)/2 = 10×9/2 = 45.

Q5. Which sorting technique requires the least additional space?
A) Merge Sort
B) Heap Sort
C) Counting Sort
D) Radix Sort
✅ Answer: B
Explanation: Heap Sort is in-place, requiring O(1) auxiliary space.

Q6. The number of comparisons in Selection Sort for n elements is:
A) n²
B) n(n−1)/2
C) log n
D) n log n
✅ Answer: B
Explanation: Selection Sort performs (n−1)+(n−2)+…+1 comparisons = n(n−1)/2.

Q7. Quick Sort’s partitioning step for n = 10 elements takes O(10). The number of such steps in the worst case is:
A) 10
B) log 10
C) 1
D) 10²
✅ Answer: A
Explanation: Each partition removes one element → n steps total.

Q8. Which sorting is preferred for linked lists?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Counting Sort
✅ Answer: A
Explanation: Merge Sort efficiently divides and merges linked lists using pointers.

Q9. Minimum number of swaps to sort [4, 3, 2, 1] using Selection Sort:
A) 3
B) 2
C) 4
D) 1
✅ Answer: A
Explanation: Selection Sort swaps only when minimum element differs → three swaps total.

Q10. Counting Sort cannot be used when:
A) Range is small
B) Data are positive integers
C) Data contain negatives
D) Data are repeated
✅ Answer: C
Explanation: Counting Sort uses index-based access → no negatives allowed unless offset.

Q11. Best-case complexity of Insertion Sort is O(n). When?
A) Array sorted ascending
B) Array sorted descending
C) Array random
D) Array identical elements
✅ Answer: A
Explanation: No shifting required for ascending sorted array.

Q12. Which sorting algorithm uses buckets or queues internally?
A) Heap Sort
B) Merge Sort
C) Radix Sort
D) Quick Sort
✅ Answer: C
Explanation: Radix Sort uses bucket/queue per digit.

Q13. Lower bound for comparison-based sorting is:
A) Ω(n log n)
B) Ω(n²)
C) Ω(log n)
D) Ω(n³)
✅ Answer: A
Explanation: Proven using decision tree model.

Q14. For n = 64 elements, approximate comparisons in Heap Sort ≈ ?
A) 384
B) 64 log₂64
C) 512
D) 128
✅ Answer: B
Explanation: O(n log n) = 64×6 = 384 comparisons.

Q15. Merge Sort on sorted input performs:
A) n
B) n log n
C) Constant
D) Unchanged comparisons
✅ Answer: B
Explanation: Merge Sort’s comparisons independent of input order.

Q16. Which is in-place but not stable?
A) Bubble Sort
B) Heap Sort
C) Insertion Sort
D) Merge Sort
✅ Answer: B
Explanation: Heap Sort changes relative order of equal keys.

Q17. In Bucket Sort, time complexity = O(n + k). What is k?
A) Number of buckets
B) Number of elements
C) Number of comparisons
D) Maximum key
✅ Answer: A
Explanation: Depends on number of buckets used.

Q18. Which sorting is adaptive?
A) Selection Sort
B) Insertion Sort
C) Merge Sort
D) Heap Sort
✅ Answer: B
Explanation: Insertion Sort’s time reduces if data nearly sorted.

Q19. If algorithm takes 49 comparisons to sort 7 elements, time complexity = ?
A) O(n²)
B) O(n log n)
C) O(n³)
D) O(log n)
✅ Answer: A
Explanation: n² = 49 → quadratic.

Q20. Which sorting is not comparison-based?
A) Merge Sort
B) Counting Sort
C) Heap Sort
D) Quick Sort
✅ Answer: B
Explanation: Counting Sort uses frequency counting.

Q21. Quick Sort is generally faster than Merge Sort because:
A) Worst case better
B) In-place partitioning reduces space overhead
C) Merge Sort uses comparisons
D) Quick Sort is stable
✅ Answer: B
Explanation: Quick Sort avoids extra arrays → faster cache performance.

Q22. Which sorting algorithm performs the same number of comparisons regardless of data order?
A) Insertion Sort
B) Selection Sort
C) Bubble Sort
D) Quick Sort
✅ Answer: B
Explanation: Selection Sort’s comparison pattern fixed.

Q23. Insertion Sort will take maximum time when input is:
A) Ascending
B) Descending
C) Random
D) Constant
✅ Answer: B
Explanation: Each element moves to front → O(n²).

Q24. The stability of a sorting algorithm means:
A) Duplicates are removed
B) Relative order of equal elements preserved
C) Memory used is less
D) Algorithm runs faster
✅ Answer: B
Explanation: Stable sorts maintain original ordering for equal keys.

Q25. Heap Sort is based on which data structure?
A) Stack
B) Tree
C) Queue
D) Graph
✅ Answer: B
Explanation: Binary Heap — a complete binary tree.

Q26. Quick Sort’s best case occurs when pivot divides array:
A) Unequally
B) Equally
C) At start
D) At end
✅ Answer: B
Explanation: Equal division → log n levels.

Q27. Which sorting algorithm does not require recursion?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Tree Sort
✅ Answer: B
Explanation: Heap Sort implemented iteratively.

Q28. Time complexity of Merge Sort recurrence T(n) = 2T(n/2) + n gives:
A) O(n log n)
B) O(n²)
C) O(log n)
D) O(n³)
✅ Answer: A
Explanation: Using Master theorem → O(n log n).

Q29. Which sorting is the slowest on average?
A) Quick Sort
B) Heap Sort
C) Merge Sort
D) Bubble Sort
✅ Answer: D
Explanation: O(n²) average, slow for large n.

Q30. Which algorithm can efficiently sort a list of 1 million integers each ≤ 1000?
A) Counting Sort
B) Quick Sort
C) Merge Sort
D) Heap Sort
✅ Answer: A
Explanation: Range small relative to n → linear-time sort.

Q31. Which of these is not an in-place sort?
A) Heap Sort
B) Merge Sort
C) Quick Sort
D) Selection Sort
✅ Answer: B
Explanation: Merge Sort requires auxiliary arrays.

Q32. Average number of passes in Bubble Sort for n = 6 sorted ascending?
A) 1
B) 0
C) 5
D) 6
✅ Answer: B
Explanation: Adaptive nature detects sorted array early → zero swaps.

Q33. What is the auxiliary space complexity of Merge Sort?
A) O(n)
B) O(1)
C) O(log n)
D) O(n log n)
✅ Answer: A
Explanation: Temporary arrays store merged halves.

Q34. Which sort works well for small datasets?
A) Quick Sort
B) Merge Sort
C) Insertion Sort
D) Heap Sort
✅ Answer: C
Explanation: Insertion Sort simple and fast for small n.

Q35. Which sorting algorithm is generally preferred for external sorting?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Selection Sort
✅ Answer: B
Explanation: Merge Sort handles disk-based (external) data effectively.

Q36. Quick Sort’s partitioning can be improved using:
A) Median-of-three
B) First element pivot
C) Last element pivot
D) Random pivot only
✅ Answer: A
Explanation: Choosing median of three elements avoids worst cases.

Q37. The number of swaps performed by Bubble Sort in best case for n = 8?
A) 28
B) 0
C) 7
D) 1
✅ Answer: B
Explanation: Already sorted → no swaps.

Q38. The algorithm used for Topological Sorting is:
A) DFS
B) Merge Sort
C) Quick Sort
D) Radix Sort
✅ Answer: A
Explanation: Based on depth-first search ordering.

Q39. Shell Sort’s worst case complexity is:
A) O(n²)
B) O(n log n)
C) O(n^(3/2))
D) O(log n)
✅ Answer: C
Explanation: Depends on gap sequence → worst O(n^(3/2)).

Q40. Which sorting is both stable and in-place?
A) Bubble Sort
B) Heap Sort
C) Merge Sort
D) Quick Sort
✅ Answer: A
Explanation: Bubble Sort stable and modifies array in place.

Q41. Which sorting uses Divide and Conquer?
A) Heap Sort
B) Merge Sort
C) Counting Sort
D) Insertion Sort
✅ Answer: B
Explanation: Divides into halves recursively.

Q42. Which sorting algorithm’s performance depends on partitioning scheme?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Counting Sort
✅ Answer: A
Explanation: Poor pivot choice → degraded performance.

Q43. The average case of Quick Sort is:
A) O(n²)
B) O(n log n)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Balanced partitions → O(n log n).

Q44. The time complexity of Bubble Sort in best case is:
A) O(n²)
B) O(n log n)
C) O(n)
D) O(1)
✅ Answer: C
Explanation: Optimized version detects no swaps.

Q45. If an array has all equal elements, time complexity of Quick Sort = ?
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
✅ Answer: B
Explanation: Every partition produces unbalanced divisions.

Q46. What will be the number of passes required by Selection Sort for 6 elements?
A) 6
B) 5
C) 4
D) 3
✅ Answer: B
Explanation: Always n−1 passes.

Q47. Merge Sort’s stability is due to:
A) No swaps
B) Merging preserves order
C) Random pivot
D) Heap property
✅ Answer: B
Explanation: During merge, left element kept first if equal.

Q48. Which sorting has minimum number of swaps in worst case?
A) Selection Sort
B) Insertion Sort
C) Bubble Sort
D) Quick Sort
✅ Answer: A
Explanation: Exactly n−1 swaps always.

Q49. Sorting n records using keys limited to 0–k uses which efficient algorithm?
A) Counting Sort
B) Heap Sort
C) Quick Sort
D) Selection Sort
✅ Answer: A
Explanation: Counting Sort suitable for small integer ranges.

Q50. In Quick Sort, tail recursion can be eliminated to reduce:
A) Space
B) Time
C) Comparisons
D) Swaps
✅ Answer: A
Explanation: Tail recursion replaced by iteration → O(log n) space.

💠 Sorting MCQs

Q51. In Merge Sort, how many merge operations are performed for 16 elements?
A) 8
B) 15
C) 16
D) 4
✅ Answer: B
Explanation: Each merge reduces array count by one → total merges = n − 1 = 15.

Q52. Which of these sorting algorithms can sort data in O(n) under specific conditions?
A) Merge Sort
B) Counting Sort
C) Heap Sort
D) Quick Sort
✅ Answer: B
Explanation: Counting Sort runs in O(n + k) if range k is small relative to n.

Q53. Which sorting algorithm works best for partially sorted data?
A) Quick Sort
B) Merge Sort
C) Insertion Sort
D) Heap Sort
✅ Answer: C
Explanation: Insertion Sort’s adaptive nature makes it ideal for nearly sorted data.

Q54. Which sorting algorithm performs minimum number of writes to memory?
A) Selection Sort
B) Merge Sort
C) Insertion Sort
D) Bubble Sort
✅ Answer: A
Explanation: Selection Sort performs at most n − 1 swaps.

Q55. The number of inversions in an array indicates:
A) Sortedness level
B) Space usage
C) Algorithm stability
D) Sorting time
✅ Answer: A
Explanation: More inversions → more disorder → worse for insertion-type sorts.

Q56. The algorithm most suitable for sorting data read from tape drives is:
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Insertion Sort
✅ Answer: A
Explanation: External Merge Sort minimizes random access and suits sequential storage.

Q57. In Heap Sort, after building the heap, how many delete-max operations are performed for n elements?
A) n
B) n − 1
C) n log n
D) log n
✅ Answer: A
Explanation: Each element is extracted once → n deletions.

Q58. Which sorting method requires knowledge of key distribution?
A) Counting Sort
B) Quick Sort
C) Heap Sort
D) Merge Sort
✅ Answer: A
Explanation: Counting Sort needs range of input keys.

Q59. Average number of comparisons in Quick Sort for n elements ≈ ?
A) n log n
B) n²
C) log n
D) n
✅ Answer: A
Explanation: Expected time complexity is O(n log n) for random pivots.

Q60. Which sorting algorithm uses a “heapify” operation?
A) Heap Sort
B) Merge Sort
C) Counting Sort
D) Quick Sort
✅ Answer: A
Explanation: Heapify constructs and maintains heap structure.

Q61. Which sorting algorithm is not suitable for linked lists due to random access requirements?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Bubble Sort
✅ Answer: B
Explanation: Quick Sort relies heavily on array indexing.

Q62. If we want to minimize comparisons, which algorithm is unsuitable?
A) Merge Sort
B) Counting Sort
C) Quick Sort
D) Heap Sort
✅ Answer: C
Explanation: Quick Sort may compare same elements multiple times.

Q63. Which sorting algorithm performs better on large datasets stored in disk files?
A) Merge Sort
B) Insertion Sort
C) Bubble Sort
D) Shell Sort
✅ Answer: A
Explanation: Merge Sort suits external (disk-based) sorting.

Q64. Which algorithm’s complexity is least affected by input order?
A) Merge Sort
B) Insertion Sort
C) Bubble Sort
D) Quick Sort
✅ Answer: A
Explanation: Merge Sort always follows same recursive steps.

Q65. In-place sorting means:
A) Sorting done with O(1) extra space
B) Sorting done recursively
C) Data copied to auxiliary array
D) Sorting done on linked lists
✅ Answer: A
Explanation: In-place sort modifies the array without extra storage.

Q66. Which algorithm has a deterministic O(n log n) time complexity in all cases?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Both A and C
✅ Answer: D
Explanation: Merge and Heap Sort both guarantee O(n log n) in all cases.

Q67. Average number of passes in Insertion Sort for n elements is approximately:
A) n/2
B) n
C) log n
D) n²
✅ Answer: A
Explanation: On average, half of the array shifts for each insertion.

Q68. Which sorting algorithm requires fewer key comparisons for small n but becomes inefficient for large n?
A) Bubble Sort
B) Insertion Sort
C) Selection Sort
D) Heap Sort
✅ Answer: B
Explanation: Insertion Sort has low overhead for small data but O(n²) scaling.

Q69. Sorting 1 million floating-point numbers is best done using:
A) Counting Sort
B) Radix Sort
C) Merge Sort
D) Heap Sort
✅ Answer: C
Explanation: Merge Sort is comparison-based and stable for floats.

Q70. The stability of Radix Sort depends on:
A) The stability of the inner sorting algorithm
B) Number of digits
C) Range of data
D) Memory size
✅ Answer: A
Explanation: Each digit-level sort must be stable for Radix Sort to work correctly.

Q71. Which sorting algorithm uses the concept of gaps?
A) Shell Sort
B) Merge Sort
C) Quick Sort
D) Heap Sort
✅ Answer: A
Explanation: Shell Sort compares elements separated by a “gap” that decreases each pass.

Q72. Which sorting algorithm can work efficiently without recursion or stack?
A) Heap Sort
B) Quick Sort
C) Merge Sort
D) Tree Sort
✅ Answer: A
Explanation: Heap Sort implemented iteratively without extra stack.

Q73. What is the height of the heap formed from n elements?
A) log n
B) n
C) n/2
D) n log n
✅ Answer: A
Explanation: Binary heap height = floor(log₂ n).

Q74. Which sorting algorithm has the least number of comparisons in the best case?
A) Insertion Sort
B) Bubble Sort
C) Merge Sort
D) Heap Sort
✅ Answer: A
Explanation: Sorted array → only n − 1 comparisons.

Q75. The total number of levels of recursion in Merge Sort for n = 64 is:
A) 6
B) 7
C) 8
D) 9
✅ Answer: B
Explanation: log₂64 = 6, but counting base level gives 7.

Q76. Which sorting technique is based on “partitioning” principle?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Counting Sort
✅ Answer: A
Explanation: Quick Sort splits data around pivot (partitioning).

Q77. Heap Sort’s best-case complexity is:
A) O(n log n)
B) O(n²)
C) O(n)
D) O(log n)
✅ Answer: A
Explanation: Heap Sort performs same operations irrespective of order.

Q78. Sorting 100 strings alphabetically is best handled by:
A) Quick Sort
B) Merge Sort
C) Counting Sort
D) Radix Sort
✅ Answer: D
Explanation: Radix Sort works efficiently for fixed-length strings.

Q79. Which sorting algorithm cannot be efficiently parallelized due to its data dependency?
A) Merge Sort
B) Quick Sort
C) Insertion Sort
D) Counting Sort
✅ Answer: C
Explanation: Insertion Sort processes elements sequentially based on previous results.

Q80. Which sorting algorithm can be easily converted into an iterative algorithm without recursion?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Both B and C
✅ Answer: D
Explanation: Iterative Merge and Heap Sorts are common.

Q81. Which algorithm uses the “divide–exchange” method?
A) Quick Sort
B) Merge Sort
C) Heap Sort
D) Radix Sort
✅ Answer: A
Explanation: Quick Sort divides and exchanges elements based on pivot.

Q82. Which sorting algorithm works efficiently for data sets with small keys but large size?
A) Counting Sort
B) Merge Sort
C) Quick Sort
D) Heap Sort
✅ Answer: A
Explanation: Counting Sort linear in n when key range small.

Q83. Quick Sort’s recursion depth for best case input size n is:
A) log n
B) n
C) √n
D) n log n
✅ Answer: A
Explanation: Balanced partition halves array → log n depth.

Q84. The sorting algorithm that requires minimum number of comparisons in best case is:
A) Insertion Sort
B) Selection Sort
C) Heap Sort
D) Merge Sort
✅ Answer: A
Explanation: Best case comparisons = n − 1.

Q85. Sorting based on LSD (least significant digit) method refers to:
A) Counting Sort
B) Radix Sort
C) Quick Sort
D) Merge Sort
✅ Answer: B
Explanation: LSD technique sorts digits from least to most significant.

Q86. Which sorting algorithm is non-stable by default but can be made stable with extra space?
A) Heap Sort
B) Selection Sort
C) Quick Sort
D) Both B and C
✅ Answer: D
Explanation: Both can be stabilized using position tracking.

Q87. The number of passes required by Bubble Sort to sort n elements is at most:
A) n
B) n − 1
C) log n
D) √n
✅ Answer: B
Explanation: After n − 1 passes, array guaranteed sorted.

Q88. Which sorting is fastest for a list of 1,000 elements when memory is not a constraint?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Counting Sort
✅ Answer: C
Explanation: Quick Sort generally fastest due to locality and cache efficiency.

Q89. Which sorting technique is particularly suitable for sorting records with multiple keys (e.g., first by name, then by age)?
A) Counting Sort
B) Radix Sort
C) Quick Sort
D) Heap Sort
✅ Answer: B
Explanation: Radix Sort performs sorting on keys sequentially by significance.

Q90. Time complexity of Radix Sort for n numbers with k digits (base b) is:
A) O(k(n + b))
B) O(n log n)
C) O(n²)
D) O(bk)
✅ Answer: A
Explanation: Each of k digit passes takes O(n + b) using stable sorting.

Q91. Which sorting algorithm works efficiently when all elements are identical?
A) Quick Sort
B) Merge Sort
C) Counting Sort
D) Insertion Sort
✅ Answer: D
Explanation: Insertion Sort finishes in O(n) for equal keys.

Q92. Shell Sort is a generalization of:
A) Bubble Sort
B) Selection Sort
C) Insertion Sort
D) Quick Sort
✅ Answer: C
Explanation: Shell Sort performs insertion sort on elements spaced by a gap.

Q93. Which sorting algorithm does not guarantee O(n log n) in all cases?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) None of these
✅ Answer: C
Explanation: Quick Sort worst-case O(n²).

Q94. Which of these is the only sorting technique suitable for online (incremental) sorting?
A) Heap Sort
B) Insertion Sort
C) Merge Sort
D) Quick Sort
✅ Answer: B
Explanation: Insertion Sort can handle new elements dynamically.

Q95. The main advantage of Merge Sort over Quick Sort is:
A) Stability and predictable performance
B) Less space requirement
C) Simplicity
D) Fewer comparisons
✅ Answer: A
Explanation: Merge Sort is stable and worst-case O(n log n).

Q96. Which algorithm is preferred for sorting very large data stored in external memory?
A) Merge Sort
B) Quick Sort
C) Heap Sort
D) Bubble Sort
✅ Answer: A
Explanation: External Merge Sort minimizes I/O operations.

Q97. Which of the following is not an in-place sorting algorithm?
A) Heap Sort
B) Quick Sort
C) Counting Sort
D) Selection Sort
✅ Answer: C
Explanation: Counting Sort uses auxiliary arrays.

Q98. The expected number of comparisons in Quick Sort when all elements are distinct is approximately:
A) 2n ln n
B) n log n
C) n²
D) log n
✅ Answer: A
Explanation: On average ≈ 2n ln n comparisons.

Q99. Which sorting algorithm’s performance is independent of input distribution?
A) Merge Sort
B) Counting Sort
C) Quick Sort
D) Insertion Sort
✅ Answer: A
Explanation: Merge Sort always divides array equally.

Q100. Which sorting algorithm can be implemented both recursively and iteratively without changing its complexity?
A) Merge Sort
B) Heap Sort
C) Quick Sort
D) Both A and C
✅ Answer: D
Explanation: Both Merge and Quick Sorts can be written iteratively or recursively with same O(n log n) behavior.