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 log 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 log n) comparisons regardless of pivot selection strategy. Assuming Selection Sort optimizes comparisons when the array is already sorted.

GATE CSE Sorting PYQs

Standard yield1.6% of Algorithms

In this topic, GATE tests the performance characteristics and comparison counts of classic sorting algorithms under specific input configurations (such as alrea… Read the guide

Take topic test

Questions: 3
Asked: since 2015
Total marks: 3
Marks / paper: 0.1

3 GATE CSE Sorting PYQs with solutions, from Algorithms. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

GATE CSE 2025 Set 1 · Q33The 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…NAT1 markEasySolve
GATE CSE 2021 Set 1 · Q9Consider 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?MCQ1 markEasyDiagramSolve
GATE CSE 2015 Set 3 · Q27Assume 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?MCQ1 markMediumSolve

What GATE tests in Sorting

Concepts, patterns, formulas and traps distilled from past papers.

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 log 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 log n))

Recurring question patterns

Time-Scaling Proportionality Calculation
OccasionalMCQ1 marks2015
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
OccasionalNAT1 marks2025
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
CommonMCQ1 marks2021
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 log 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 log 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.