Sorting arranges data in order; stability preserves equal-key order, in-place operation limits extra memory, and external sorting handles data that exceeds memory. Quick questions test what sorting means, what makes a sort stable, how in-place differs from stable, and where standard algorithms fit the complexity table.
Use the Introduction to Sorting practice module to test these distinctions before reading the explanations below. Start by identifying the property being asked about: ordering, stability, memory use, data location, or running time.
What sorting actually means
Sorting rearranges a collection into an order, such as ascending, descending, or lexicographic by a key. Sorted data then supports binary search instead of a full scan.
Q1. Definition of sorting
Source: Kendriya Vidyalaya Sangathan 2013
Sorting is
A. a process of re-arranging a given set of objects in a specific order.
B. to facilitate the later search for members of the sorted set.
C. is a relevant and essential activity, particularly in data processing.
D. All of these
Answer: A. Option A gives the definition. B is a benefit and C gives a context, so their true-sounding language does not make D correct.
Stable sorting, the definition exams repeat most
A sort is stable if records with the same key keep their relative order. This matters when data is sorted by more than one key.
Sort (3,a) (1,b) (3,c) (2,d) (1,e) by key. The stable output (1,b) (1,e) (2,d) (3,a) (3,c) keeps b before e and a before c. An unstable result could reverse those equal-key tags.
Q2. Stable sorting in GATE wording
Source: GATE 1999
A sorting technique is called stable if:
A. It takes O(n log n) time
B. It maintains the relative order of occurrence of non-distinct elements
C. It uses divide and conquer paradigm
D. It takes O(n) space
Answer: B. Stability describes the order of equal elements. Time, space, and the algorithmic design paradigm are separate properties.
Q3. The same definition in an ISRO item
Source: Indian Space Research Organization December 2017
A sorting technique is called stable if
A. If it takes O(n log n) time
B. It uses divide and conquer technique
C. Relative order of occurrence of non-distinct elements is maintained
D. It takes O(n) space
Answer: C. The key phrase is “relative order of occurrence of non-distinct elements”. The options merely reshuffle the same distinction tested in Q2.
Q4. Stable sorting and duplicate keys
Source: Coal India 2020. Open this question in the GATE module.
What is mean by stable sorting algorithm?
A. A sorting algorithm is stable if it preserves the order of all keys
B. A sorting algorithm is stable if it preserves the order of non-duplicate keys
C. A sorting algorithm is stable if it preserves the order of duplicate keys
D. A sorting algorithm is stable if it doesn't preserve the order of duplicate keys
Answer: C. Duplicate, or equal, keys are the defining case. Distinct keys take their sorted positions regardless of stability, while D states the opposite property.
Recognising stable and unstable sorts
Question setters reskin the stable-sort definition. Recognise the equal-element order test under new wording.
Q5. Original order after sorting
A sorting algorithm is said to be stable when:
A. It requires time complexity of O(n log n)
B. It is based on the divide and conquer approach
C. It preserves the original order of equal elements after sorting
D. It needs O(n) extra space
Answer: C. Only C talks about the original order of equal elements. The other options describe complexity, technique, or memory use.
Q6. Stability in plain words
Source: CoCubes 2025
A stable sorting algorithm
A. does not crash.
B. does not run out of memory.
C. does not change the sequence of appearance of elements.
D. does not exists.
Answer: C. Here “sequence of appearance” expresses relative order. Crashes and memory exhaustion concern robustness, not stability.
Q7. Identify the unstable algorithm
Which of the following is not a stable sorting algorithm in its typical implementation?
A. Insertion sort
B. Merge sort
C. Quick sort
D. Bubble sort
Answer: C. Typical Quick Sort partitioning can move equal elements past one another. Insertion sort, merge sort, and bubble sort preserve equal-key order in their standard stable implementations.
In-place versus stable: do not mix them up
In-place means using only O(1) extra memory. Stable means preserving equal-key order. An algorithm can be either, both, or neither.
Q8. The swapped-definitions trap
Open this question in the placement module.
Which of the following statements is/are true? S1. A sorting algorithm is in-place if the relative order of common elements is maintained after sorting. S2. A sorting algorithm is stable if it requires very little additional space besides the initial array holding the elements that are to be sorted.
A. Only S1
B. Only S2
C. Both S1 & S2
D. Neither S1 nor S2
Answer: D. The definitions are swapped. S1 describes stability and S2 describes in-place behaviour, so neither statement is true as written.
Internal versus external sorting
Internal sorts keep all data in memory. External sorts move runs to and from disk when data exceeds RAM. Merge sort is the classic external choice because it merges runs sequentially. Compare the internal methods in Sorting Algorithms: Complexity and Comparison.
Q9. Identify the external sort
Source: BEL Probationary Engineer 2023. Open this question in the placement module.
Which of the following is the external sorting?
A. Insertion sort
B. Merge sort
C. Quick sort
D. Selection sort
Answer: B. Insertion, quick, and selection sort are normally used in memory. Merge sort supports sequential merging of disk-based runs, making it the standard external sort here.
The complexity-matching question
Keep these four algorithm and average-order pairs clear:
Routine | Average order |
|---|---|
Binary search | O(log n) |
Quick sort | O(n log n) |
Linear search | O(n) |
Selection sort | O(n^2) |
Q10. Match each algorithm to its average complexity
Source: BEL Probationary Engineer 2023. Open this question in the GATE module.
Match the following algorithm with its average complexity. Algorithm / Average Complexity: I. Binary search / 1. O(n^2); II. Quick sort / 2. O(log n); III. Linear search / 3. O(n log n); IV. Selection sort / 4. O(n)
A. I - 4; II - 3; III - 2; IV - 1
B. I - 2; II - 3; III - 4; IV - 1
C. I - 1; II - 4; III - 2; IV - 3
D. I - 3; II - 1; III - 2; IV - 4
Answer: B. Binary search halves the range, so I-2. Quick sort averages O(n log n), so II-3, although its worst case is O(n^2). Linear search gives III-4, and selection sort’s nested scans give IV-1.
A worked counting question from GATE
This exchange-counting problem needs a two-pointer argument, not a memorised definition.
Take arr = [-3, 5, -2, 7, -8, 1], with n = 6. The goal is to put every negative before every positive using the fewest swaps.
The left pointer stops at index 1, value
5, and the right pointer stops at index 4, value-8.Swap them to get
[-3, -8, -2, 7, 5, 1].Left advances to index 3 and right retreats to index 2. They have crossed, so stop.
This input takes one swap. For six values, the worst arrangement [+, +, +, -, -, -] needs three swaps: positions 0 with 5, 1 with 4, and 2 with 3. Each fixes two misplaced elements, so the ceiling is floor(n/2). Here floor(6/2) = 3, below n - 1 = 5, n = 6, and n + 1 = 7.
![Worst-case array [+ + + - - -] needs three swaps pairing indices 0-5, 1-4, and 2-3, illustrating floor(n/2) exchanges.](https://cdn.knowledgegate.ai/blog-assets/blog_asset_1784136076732_a0xf1u.jpg)
Q11. Minimum exchanges in the worst case
Source: GATE 1999
Suppose we want to arrange the n numbers stored in an array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is:
A. n - 1
B. n
C. n + 1
D. None of the above
Answer: D. The two-pointer partition requires at most floor(n/2) exchanges because every swap fixes two misplaced elements. That number is smaller than all three numeric choices, so none of them is correct.
Sorting MCQs: the short version and your next step
Keep four tests separate: equal-key order means stability, constant auxiliary storage means in-place operation, disk-sized input points to external sorting, and a time bound must be tied to a named routine. For exchange questions, mark misplaced values at both ends and count how many pairs one swap fixes.
For deeper work on stability, in-place behaviour, and complexity, continue with GATE Guidance by Sanchit Sir and the GATE CS Exam Preparation Courses & Test Series. For timed campus and PSU practice, use Coding for Placements, C, C++, Java, Python.
For more free practice, try Data Structures MCQs. Memorise the definitions, keep independent properties separate, and trace pointers whenever a question asks for exchanges.
