Sorting Algorithms - Practice MCQs for CCAT

Correct Answer: B - Merge Sort

Merge Sort is stable - maintains relative order of equal elements.

Correct Answer: B - O(n)

With optimization, Bubble Sort is O(n) for already sorted array.

Correct Answer: C - Quick Sort

Quick Sort is in-place (O(log n) stack space) with O(n log n) average.

Correct Answer: A - O(n)

Merge Sort needs O(n) auxiliary space for merging.

Correct Answer: B - Merge Sort

Merge Sort and Quick Sort use divide and conquer approach.

Correct Answer: A - O(n log n)

Heap Sort is O(n log n) in all cases (best, average, worst).

Correct Answer: A - Small range of integers

Counting Sort works best when range of values is small (0 to k).

Correct Answer: D - Nearly sorted small arrays

Insertion Sort is O(n) for nearly sorted arrays and good for small data.

Correct Answer: C - Quick Sort

Quick Sort has O(n²) worst case when pivot selection is poor.

Correct Answer: B - O(nk)

Radix Sort is O(nk) where k is number of digits in max element.

Correct Answer: B - Insertion Sort

Insertion Sort is adaptive - it performs better on partially sorted arrays.

Correct Answer: B - Insertion Sort

Shell Sort improves Insertion Sort by comparing elements at gaps, reducing inversions faster.

Correct Answer: B - Counting Sort

Counting Sort uses counting, not comparisons, making it a non-comparison sort.

Correct Answer: D - Median-of-three

Median-of-three (first, middle, last) helps avoid worst case on sorted/reverse arrays.

Correct Answer: D - O(n + k)

Bucket Sort is O(n + k) average where k is number of buckets, assuming uniform distribution.

Correct Answer: B - Merge Sort

Merge Sort is ideal for linked lists as it doesn't need random access and works well with sequential data.

Correct Answer: B - O(n)

Selection Sort makes at most n-1 swaps (one per pass), giving O(n) swaps.

Correct Answer: A - Merge and Insertion

Tim Sort combines Merge Sort with Insertion Sort for small runs, used in Python and Java.

Correct Answer: D - Merge Sort

Merge Sort has O(n log n) comparisons even in worst case, optimal for comparison sorts.

Correct Answer: D - Data is too large for memory

External sorting (like external merge sort) is used when data doesn't fit in main memory.

Correct Answer: D - O(n²)

Bubble Sort has O(n²) worst-case time complexity, occurring when the array is sorted in reverse order, requiring maximum swaps.

Correct Answer: C - Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted portion and placing it at the beginning of the unsorted part.

Correct Answer: D - O(n)

With the optimization of stopping when no swaps occur in a pass, Bubble Sort achieves O(n) best-case time when the array is already sorted.

Correct Answer: A - Divide and Conquer

Merge Sort uses Divide and Conquer: it divides the array into halves, recursively sorts them, and merges the sorted halves.

Correct Answer: C - O(n log n)

Merge Sort has O(n log n) time complexity in best, average, and worst cases. The divide step takes O(log n) levels and merging takes O(n) at each level.

Correct Answer: B - O(n)

Merge Sort requires O(n) additional space for the temporary arrays used during merging. It is not an in-place sorting algorithm.

Correct Answer: C - O(n²)

Quick Sort's worst case is O(n²), occurring when the pivot is always the smallest or largest element (e.g., sorted array with first/last element as pivot).

Correct Answer: A - O(n log n)

On average, Quick Sort achieves O(n log n) time complexity when pivots reasonably divide the array into balanced partitions.

Correct Answer: D - Selection Sort

Selection Sort is not stable because it may change the relative order of equal elements during the swap operation.

Correct Answer: A - Equal elements maintain their relative order

A stable sorting algorithm preserves the relative order of elements with equal keys, which is important when sorting by multiple criteria.

Correct Answer: C - Quick Sort

Quick Sort is generally the fastest in practice due to its good cache performance, low constant factors, and O(n log n) average case.

Correct Answer: A - The array is nearly sorted

Insertion Sort performs best on nearly sorted arrays, achieving close to O(n) time as very few shifts are needed.

Correct Answer: C - O(n²)

Insertion Sort has O(n²) worst-case complexity when the array is sorted in reverse order, requiring maximum shifts for each element.

Correct Answer: C - Time complexity

The pivot choice significantly affects Quick Sort's performance. A bad pivot (extreme element) leads to O(n²), while a good pivot gives O(n log n).

Correct Answer: C - Quick Sort

Quick Sort is an in-place sorting algorithm that uses only O(log n) extra space for the recursion stack. It partitions the array without needing extra arrays.

Correct Answer: D - Correct sorted position

After partitioning, the pivot element is placed in its correct final sorted position, with all smaller elements before it and all larger elements after it.

Correct Answer: A - Merge Sort

Merge Sort always has O(n log n) time complexity regardless of the input, as it always divides and merges in the same manner.

Correct Answer: C - n(n-1)/2

Selection Sort makes (n-1) + (n-2) + ... + 1 = n(n-1)/2 comparisons regardless of the input order.

Correct Answer: B - T(n) = 2T(n/2) + n

Merge Sort divides the array into two halves (2T(n/2)) and merges them in O(n) time, giving the recurrence T(n) = 2T(n/2) + n.

Correct Answer: A - Selection Sort

Selection Sort performs at most n-1 swaps (one per pass), which is the minimum among comparison-based O(n²) sorting algorithms.

Correct Answer: B - O(n log n)

The theoretical lower bound for any comparison-based sorting algorithm is Ω(n log n). No comparison-based sort can do better in the worst case.

Correct Answer: A - Repeatedly swapping adjacent elements if they are in wrong order

Bubble Sort works by repeatedly stepping through the list, comparing adjacent elements, and swapping them if they are in the wrong order.

Correct Answer: C - Already sorted array with first element as pivot

Quick Sort performs worst on an already sorted array when the first (or last) element is chosen as pivot, creating maximally unbalanced partitions.

Correct Answer: A - It always makes O(n²) comparisons

Selection Sort always makes n(n-1)/2 comparisons regardless of input order, making its time complexity O(n²) in all cases.

Correct Answer: D - O(n)

The best case for Insertion Sort is O(n) when the array is already sorted, as each element requires only one comparison and no shifts.

Correct Answer: C - Worst case guarantee is important

Merge Sort is preferred when worst-case O(n log n) guarantee is important, as Quick Sort can degrade to O(n²) in the worst case.

Correct Answer: D - Quick Sort

Quick Sort uses a 'pivot' (key element) to partition the array into two parts: elements less than the pivot and elements greater than the pivot.

Correct Answer: A - n - 1

Bubble Sort needs n-1 passes in the worst case. After each pass, the largest unsorted element bubbles to its correct position.

Correct Answer: B - Insertion Sort

Insertion Sort is adaptive — its performance improves when the input is partially sorted, achieving O(n) for nearly sorted data.

Correct Answer: D - O(log n)

Quick Sort uses O(log n) space in the best/average case for the recursion stack when partitions are balanced. Worst case is O(n) for skewed partitions.