What are common examiner traps in Sorting?

Unit conversion errors between seconds and minutes when computing time bounds (e.g., forgetting to convert 6 minutes to 360 seconds). Off-by-one errors in nested loop iteration counts (e.g., using n(n+1)/2 instead of n(n-1)/2). Assuming base-10 instead of base-2 for n when evaluating powers-of-two input sizes. Failing to inspect the input array to notice that it is already sorted in non-decreasing order. Confusing Quicksort's best-case and worst-case behaviors, particularly assuming Quicksort always takes O(n n) comparisons regardless of pivot selection strategy. Assuming Selection Sort optimizes comparisons when the array is already sorted.

Sorting

3 Qs · since 2015 · 3 marks · 0.1 marks/paperStandard yield

Take topic test

In this topic, GATE tests the performance characteristics and comparison counts of classic sorting algorithms under specific input configurations (such as already sorted arrays). Q… Guide

Type

GATE CSE 2025 Set 1Q33NAT1 markEasyThe pseudocode of a function fun() is given below: fun(int A[0,...,n-1]){ for i=0 to n-2 for j=0 to n-i-2 if (A[j]>A[j+1]) then swap A[j] and A[j+1] } Let $A[0, \dots, 29]$ be an array storing 30 distinct integers in descending order. The number of…
GATE CSE 2021 Set 1Q9MCQ1 markEasyDiagramConsider the following array. Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
GATE CSE 2015 Set 3Q27MCQ1 markMediumAssume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

Topic guide

What does GATE test in Sorting?

In this topic, GATE tests the performance characteristics and comparison counts of classic sorting algorithms under specific input configurations (such as already sorted arrays). Questions focus on identifying best-case vs. worst-case behaviors, comparison complexity bounds, and algorithm-specific adaptability.

Core concepts

Merge Sort worst-case time complexity O(n n) and execution time scaling
Bubble Sort loop bounds and conditional swap execution
Worst-case descending order input and inversion counting
Best-case and worst-case comparison complexity of Insertion Sort
Data-insensitivity of Selection Sort comparisons
Quicksort worst-case behavior under sorted input and deterministic pivot choice
Mergesort comparison bounds (O(n n))

Recurring question patterns

Time-Scaling Proportionality Calculation
occasional · MCQ · 1 marks · 2015
Given the execution time of a comparison-based sort (like Merge Sort) for a specific input size $n_1$ , calculate the maximum input size $n_2$ solvable within an expanded time limit assuming $T(n) = c \cdot f(n)$ .
Pseudocode Operation Counting
occasional · NAT · 1 marks · 2025
Given a sorting loop structure (such as nested loops of Bubble Sort) and a specific input configuration (such as reverse sorted array), calculate the exact number of key operations (comparisons or swaps) executed.
Comparison Count on Specific Input Presets
common · MCQ · 1 marks · 2021
An input array with specific properties (e.g., pre-sorted array) is provided, and the candidate must evaluate which sorting algorithm performs the minimum or maximum number of element comparisons.

Formulas GATE uses

Merge Sort Running Time Relation

T(n) = c \cdot n \log_2 n

Used to compute scaling factor $c$ and solve for target problem size $n$ given execution time.

Worst-case Bubble Sort Swaps (Inversion Count)

\sum_{i=0}^{n-2} (n - 1 - i) = \frac{n(n - 1)}{2}

Used to calculate the exact number of swap operations performed by standard bubble sort on a strictly decreasing array of size $n$ .

Insertion Sort Best-Case Comparisons

C_{\text{best}} = n - 1

Calculated when the input array is already sorted in ascending order.

Selection Sort Total Comparisons

C = \frac{n(n-1)}{2}

Evaluated for Selection Sort regardless of input order as it always scans the remaining unsorted subarray.

Quicksort Worst-Case Comparisons (End Pivot on Sorted Array)

C_{\text{worst}} = \frac{n(n-1)}{2}

Evaluated when an already sorted array is partitioned using the first or last element as the pivot.

Examiner traps in Sorting

Unit conversion errors between seconds and minutes when computing time bounds (e.g., forgetting to convert 6 minutes to 360 seconds).
Off-by-one errors in nested loop iteration counts (e.g., using n(n+1)/2 instead of n(n-1)/2).
Assuming base-10 instead of base-2 for n when evaluating powers-of-two input sizes.
Failing to inspect the input array to notice that it is already sorted in non-decreasing order.
Confusing Quicksort's best-case and worst-case behaviors, particularly assuming Quicksort always takes O(n n) comparisons regardless of pivot selection strategy.
Assuming Selection Sort optimizes comparisons when the array is already sorted.

How questions are asked

Proportionality time-limit calculation
Pseudocode tracing and exact operation counting
Identifying the sorting algorithm with minimal comparisons for a given array

Paper trends

Shift from multiple-choice questions on asymptotic scaling ratios to numerical answer type (NAT) questions assessing exact step counts on standard sorting pseudocode.
2025, 2015
Questions test fundamental behavior by presenting an explicit array to verify whether candidates recognize pre-sorted inputs and map them to the best-case time and comparison complexity of standard algorithms.
2021

Difficulty notes

Easy questions require standard formula application such as $n(n-1)/2$ for loop bounds on an array of size $n$ . Medium questions involve multi-step arithmetic where constants must be resolved and non-linear equations (like $n \log_2 n = K$ ) matched against power-of-two choices.