programming
beginner
10 sample questions
Sorting Algorithms MCQ Practice Test
Bubble Sort: How it works and its time complexity.
QuickSort: Key steps in the sorting process and why it’s efficient for large datasets.
Merge Sort: Comparing it with other sorting algorithms and its use case for stable sorting.
Q1. Timsort, the built-in sorting algorithm of Python and (in variant form) Java, is a hybrid built from which two algorithms?
-
A. Merge sort and insertion sort ✓
-
B. Merge sort and heap sort
-
C. Quicksort and insertion sort
-
D. Heap sort and bubble sort
Explanation: Timsort detects naturally occurring ordered runs, extends short runs with binary insertion sort, and merges the runs with merge sort, giving O(n log n) worst case and O(n) on already-sorted data. Quicksort + heapsort + insertion sort is introsort, used by C++ std::sort.
Q2. You are sorting a list of integers using Bubble Sort. The list is [5, 2, 8, 1, 9, 4]. After the first pass of the algorithm, what will the list look like?
-
A. [2, 5, 1, 8, 4, 9] ✓
-
B. [5, 2, 8, 1, 4, 9]
-
C. [1, 2, 4, 5, 8, 9]
-
D. [5, 2, 1, 8, 4, 9]
Explanation: First pass of bubble sort on [5,2,8,1,9,4]: swap 5/2 → [2,5,8,1,9,4]; 5/8 stay; swap 8/1 → [2,5,1,8,9,4]; 8/9 stay; swap 9/4 → [2,5,1,8,4,9].
Q3. Given an array of integers, which sorting algorithm has an average and worst-case time complexity of O(n^2) but performs well for nearly sorted inputs with a time complexity of O(n)?
-
A. Merge Sort
-
B. Heap Sort
-
C. Insertion Sort ✓
-
D. Timsort
Explanation: Insertion Sort has an average and worst-case time complexity of O(n^2), but it performs well for nearly sorted inputs with a time complexity of O(n) because it only needs to shift a few elements.
Q4. In a heap sort implementation, what is the time complexity of the heapify operation on a single node when the input array is already a max heap?
-
A. O(n log n)
-
B. O(n)
-
C. O(1)
-
D. O(log n) ✓
Explanation: When the input array is already a max heap, heapify on a single node still needs to compare the node with its children and potentially swap to maintain the heap property. The maximum number of comparisons and swaps is proportional to the height of the heap, which is O(log n).
Q5. To arrange an array of building heights from tallest to shortest, which algorithm repeatedly selects the maximum remaining height and places it next in the sorted portion?
-
A. Bubble sort with a twist that it only compares adjacent buildings if they are not of the same height
-
B. Selection sort that chooses the maximum height building at each step ✓
-
C. Insertion sort that inserts each building to its correct position based on its height
-
D. Merge sort that splits the array into smaller chunks and merges them back in sorted order
Explanation: Selection sort for descending order repeatedly finds the maximum of the unsorted portion and swaps it into place - exactly the described process; the other options do not select the maximum at each step.
Q6. In the context of the Merge Sort algorithm, what is the time complexity of the merge step, assuming the input is already partially sorted?
-
A. O(n) ✓
-
B. O(n log n)
-
C. O(n^2)
-
D. O(log n)
Explanation: The merge step in Merge Sort has a time complexity of O(n), as it only requires a single pass through the partially sorted input to merge the two halves. This is because the input is already partially sorted, reducing the number of comparisons needed.
Q7. Given an array of integers, what is the time complexity of the “Timsort” algorithm when the input array is already sorted?
-
A. O(n log n)
-
B. O(n) ✓
-
C. O(log n)
-
D. O(1)
Explanation: Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort. When the input array is already sorted, Timsort's performance is similar to that of insertion sort, which has a time complexity of O(n) in the best case, where n is the number of elements in the array.
Q8. Given an array of integers, which sorting algorithm has an average time complexity of O(n log n) and a worst-case time complexity of O(n log n), but is known to perform well when the input array is already partially sorted?
-
A. Heap sort
-
B. Timsort ✓
-
C. Insertion sort
-
D. Bubble sort
Explanation: Timsort is a hybrid sorting algorithm derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data. It has a worst-case time complexity of O(n log n) and is known to perform well when the input array is already partially sorted, making it a good choice for adaptive sorting.
Q9. Given an array of integers, which of the following sorting algorithms has a time complexity of O(n) in the best case when the input array is already sorted?
-
A. Merge sort
-
B. Quick sort
-
C. Heap sort
-
D. Bubble sort ✓
Explanation: Bubble sort has a time complexity of O(n) in the best case, which occurs when the input array is already sorted. In this scenario, the algorithm only needs to iterate through the array once to confirm its sorted state.
Q10. Given an array of integers, which sorting algorithm has a time complexity of O(n log k) in the best case, where n is the number of elements and k is the number of elements in the subarray being considered?
-
A. Heap Sort with a binary heap of size k ✓
-
B. Merge Sort with a divide-and-conquer approach
-
C. Radix Sort with a bucketing strategy
-
D. Timsort with a hybrid approach
Explanation: This question requires knowledge of the time complexity of different sorting algorithms. Heap Sort with a binary heap of size k has a time complexity of O(n log k) in the best case, making it the correct answer.
That was just a sample. Sign up to unlock the full question bank with timed tests and certificates.
Sign Up Free