Sorting Notes & Formulas

1. Foundational Taxonomies in Sorting

In the rigorous landscape of the GATE (Graduate Aptitude Test in Engineering), strategic classification is the bedrock of performance. Algorithmic taxonomies are not merely definitional; they form the basis of "Correct/Incorrect" statement-type questions that frequently appear in the Technical section. A candidate's ability to deconstruct an algorithm into its core properties is the primary filter used to eliminate distractor options under time pressure.

Core Properties:

• Stability: A sorting algorithm is stable if it preserves the relative order of records with equal keys. Formally, if $A[i] = A[j]$ and $i < j$ in the input, then $A[i]$ must appear before $A[j]$ in the output. This is critical for multi-key sorting (e.g., sorting by name, then by rank).
• In-place vs. Out-of-place: An in-place algorithm (e.g., Selection Sort, Heap Sort) requires no auxiliary data structure to store a copy of the input, typically characterized by $O(1)$ or $O(\log n)$ auxiliary space. Conversely, out-of-place algorithms (e.g., Merge Sort) require $O(n)$ extra space.
• Adaptive vs. Non-adaptive: An adaptive algorithm's performance improves when the input possesses existing order. For example, Insertion Sort is highly adaptive ($O(n)$ best case), whereas Selection Sort is non-adaptive ($O(n^2)$ regardless of input).
• Comparison vs. Non-comparison: Comparison-based algorithms rearrange elements by comparing keys, hitting a theoretical lower bound of $\Omega(n \log n)$. Non-comparison sorts (Counting, Radix, Bucket) bypass this bound to achieve linear time by making assumptions about the data range.

2. Core Algorithmic Philosophies

Sorting strategies generally fall into three distinct paradigms: Incremental, Divide-and-Conquer, and Partitioning.
The Incremental approach (Selection and Insertion Sort) builds a sorted solution one element at a time, expanding the sorted frontier. The Divide-and-Conquer paradigm, exemplified by Merge Sort, splits the problem into equal halves ($n/2$), sorts them recursively, and merges the results. Partitioning, the soul of Quick Sort, differs fundamentally: while Merge Sort divides by position, Quick Sort divides by value relative to a 'pivot'.

These philosophies extend beyond sorting; the partitioning logic is the mathematical basis for Quick-Select, used to find the $k^{\text{th}}$ smallest element in $O(n)$ average time. Mastering these philosophies allows us to predict how modifications to the sorting logic will impact the resulting recurrence relations.

3. Essential Properties and Theoretical Limits

Complexity bounds are the "make-or-break" factors in algorithm selection. For any comparison-based sort, we can model the process as a Decision Tree.
For $n$ elements, there are $n!$ possible permutations (leaves). To distinguish between these permutations, a binary tree must have a height $h$ such that $2^h \ge n!$. Applying Stirling's Approximation ($\log(n!) \approx n \log n - n \log e$): $h \ge \log(n!) \approx n \log n$. Thus, the comparison lower bound is mathematically established as $\Omega(n \log n)$.

GATE Shortcut: Diagnostic Patterns

• The Inversion Relationship: For adjacent-swap algorithms (Bubble/Insertion), the number of swaps is exactly equal to the number of inversion pairs ($i < j$ but $A[i] > A[j]$).
• Memory Efficiency: If $O(1)$ auxiliary space is a constraint, Merge Sort is automatically disqualified.
• The Sorted-Input Trap: Already-sorted or reverse-sorted arrays often trigger the worst-case behavior in non-adaptive $O(n^2)$ algorithms or poorly implemented Quick Sort.

4. Elementary Sorts: Bubble, Selection, and Insertion

Despite their $O(n^2)$ average complexity, these remain highly relevant in GATE due to their specific behaviors regarding swaps and stability.

Bubble Sort:

• Complexity: Best: $O(n)$ (adaptive with flag), Avg/Worst: $O(n^2)$.
• GATE Trap: Number of swaps = Number of inversion pairs.

Selection Sort:

• Complexity: Best/Avg/Worst: $O(n^2)$.
• The "So What?" Layer: It is NOT stable. Example: $[2_a, 2_b, 1] \rightarrow [1, 2_b, 2_a]$. However, it is the most swap-efficient algorithm, requiring only $O(n)$ swaps even in the worst case.

Insertion Sort:

• Complexity: Best: $O(n)$ (already sorted), Avg/Worst: $O(n^2)$.
• The "So What?" Layer: Highly adaptive. It is the preferred choice for nearly sorted data where the number of inversions is small ($O(n+k)$ where $k$ is inversions).

5. Merge Sort: The Stable Powerhouse

Merge Sort provides a guaranteed $O(n \log n)$ performance, making it the gold standard for reliability and external sorting.

• Recurrence: $T(n) = 2T(n/2) + \Theta(n)$.
• Master Theorem Analysis: Here $a=2, b=2, f(n)=n^1$. Since $n^{\log_b a} = n^{\log_2 2} = n^1$, this is Case 2, giving $T(n) = \Theta(n \log n)$.
• The Merge Procedure: Merges two sorted arrays $L$ and $R$ into $A$ in $\Theta(n)$ time by comparing the head of each sub-array and moving the smaller element.
• Critical Disadvantage: Space complexity is $O(n)$ because the merge process cannot easily be done in-place without increasing time complexity.

6. Quick Sort: Partition-Based Efficiency

Quick Sort's average-case speed stems from excellent cache locality, though it is vulnerable to poor pivot selection.

Partitioning Pseudocode (Lomuto):

Partition(A, p, r):
    x = A[r] // Pivot
    i = p - 1
    for j = p to r - 1:
        if A[j] <= x:
            i++, swap A[i] with A[j]
    swap A[i+1] with A[r]
    return i + 1

Performance Cases:

• Best Case ($O(n \log n)$): Pivot consistently splits the array into equal halves.
• Worst Case ($O(n^2)$): Array is already sorted and the first/last element is chosen as the pivot, leading to a skewed recurrence: $T(n) = T(n-1) + n$.
• Randomized Quick Sort: By choosing a pivot at random, we ensure an expected time of $O(n \log n)$ regardless of the input distribution.
• GATE Trap: Quick Sort is often called "in-place," but its space complexity is actually $O(\log n)$ due to the recursion stack.

7. Heap Sort: Priority-Queue Driven Sorting

Heap Sort treats the input array as a Complete Binary Tree and maintains the Heap Property.

Representation: For a node at index $i$:

• $\text{Left Child} = 2i + 1$
• $\text{Right Child} = 2i + 2$
• $\text{Parent} = \lfloor (i-1)/2 \rfloor$

Procedures:

• MaxHeapify(A, i, n): A top-down traversal to maintain the max-heap property ($O(\log n)$).
• BuildHeap(A): Starts from the first non-leaf node ($\lfloor n/2 \rfloor - 1$) and calls MaxHeapify down to the root ($O(n)$).
• Performance: Consistently $O(n \log n)$ and in-place ($O(1)$ space). However, it is typically slower than Quick Sort in practice because of poor cache locality.

8. Non-Comparison Sorting: Breaking the $\Omega(n \log n)$ Barrier

By assuming properties about the input range, we can achieve $O(n)$ time.

• Counting Sort: Uses an auxiliary array to count frequencies. Time: $O(n+k)$ where $k$ is the range of integers.
• Radix Sort: Sorts digit-by-digit using a stable sort (like Counting Sort) as a subroutine. Time: $O(d(n+k))$.
• Bucket Sort: Distributes elements into buckets and sorts them individually.

9. The Master Comparison Matrix

| Algorithm | Best Time | Avg Time | Worst Time | Space | Stable | In-place | Adaptive |
| :--- | :--- | :--- | :--- | :--- | :--- | :--- | :--- |
| Bubble | $O(n)$ | $\Theta(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes | Yes |
| Selection | $O(n^2)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | No | Yes | No |
| Insertion | $O(n)$ | $O(n^2)$ | $O(n^2)$ | $O(1)$ | Yes | Yes | Yes |
| Merge | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(n)$ | Yes | No | No |
| Quick | $O(n \log n)$ | $O(n \log n)$ | $O(n^2)$ | $O(\log n)$ | No | Yes | No |
| Heap | $O(n \log n)$ | $O(n \log n)$ | $O(n \log n)$ | $O(1)$ | No | Yes | No |

Typical Use Cases:

• Linked Lists: Merge Sort (no extra space for pointers).
• Small Arrays: Insertion Sort (low overhead).
• Large Range Integers: Radix Sort (e.g., sorting 32-bit keys in passes).

10. Complexity Analysis & Recurrence Deep Dive

GATE frequently tests the mathematical verification of these complexities through recurrences.

• Binary Search: $T(n) = T(n/2) + c \implies \Theta(\log n)$ (Case 2, $k=0$).
• Merge Sort: $T(n) = 2T(n/2) + n \implies \Theta(n \log n)$ (Case 2, $k=1$).
• Quick Sort (Worst): $T(n) = T(n-1) + n \implies \Theta(n^2)$.
• Quick Sort (Skewed): $T(n) = T(n/4) + T(3n/4) + cn \implies \Theta(n \log n)$. This "unbalanced" partition still results in $n \log n$ as long as the split is in a constant ratio.

11. Sorting Problem Identification Strategy

• Is $O(n)$ best case required? $\rightarrow$ Use Insertion Sort.
• Is minimum swaps required? $\rightarrow$ Use Selection Sort ($O(n)$ swaps).
• Is space strictly $O(1)$ and time $O(n \log n)$? $\rightarrow$ Use Heap Sort.
• Is the data on external disk? $\rightarrow$ Use External Merge Sort.
• Are keys small integers? $\rightarrow$ Use Counting Sort.

12. Classic GATE Problem Patterns

• Inversion Counting: A modified Merge Sort can count inversions in $O(n \log n)$ by counting how many elements from the right sub-array are jumped over during the merge.
• Quick-Select: To find the $k^{\text{th}}$ smallest element, we only recurse into one sub-partition. $T(n) = T(n/2) + n \implies O(n)$ average time.
• Nearly Sorted Comparison: Insertion Sort ($O(n)$) always outperforms Quick Sort ($O(n^2)$) if the pivot strategy is naive and data is nearly sorted.

13. Advanced Exam Concepts

• External Merge Sort: Data is divided into "runs" that fit in RAM, sorted, and then merged using a multi-way merge.
• Hybrid Sorts: Practical implementations (like Timsort) use Merge/Quick sort but switch to Insertion Sort for sub-arrays where $n \approx 10$ to minimize recursion overhead.

14. Common GATE PYQ Pattern Analysis

• The Swap Differentiator (ISRO 2017): Bubble Sort swaps equal the number of inversions. Selection sort always swaps $O(n)$.
• Non-Standard Partitioning (GATE 2009): If partitioning always selects the $n/4^{\text{th}}$ element, the recurrence $T(n) = T(n/4) + T(3n/4) + n$ yields $\Theta(n \log n)$. This is a common high-difficulty "Statement" question.
• Heap Verification: Given an array, is it a Max-Heap? Check parent-child indices: $A[i] \ge A[2i+1]$ and $A[i] \ge A[2i+2]$ for all $i < n/2$.

15. Fast Revision Cheat Sheet

Complexity & Stability Snapshot:

• Stable: Bubble, Insertion, Merge.
• Unstable: Selection, Quick, Heap.
• Worst-Case $O(n \log n)$: Merge, Heap.

Most Repeated PITFALLS:

• Quick Sort Worst Case: It is not $O(n \log n)$ on sorted data unless randomized.
• Merge Sort Space: It is not in-place; $O(n)$ is a significant memory penalty.
• Selection Sort Stability: It is the only elementary sort that is typically unstable.

Pattern Recognition Tricks:

• If swaps = inversions: Directly implies an $O(n^2)$ complexity bound characterized by adjacent-element parity (Bubble Sort).
• Binary Search vs. Heapify: Both are $O(\log n)$. However, Heapify is a top-down tree traversal maintaining the heap property, while Binary Search is a range-halving search on a linear sorted array.
• Decision Tree: A comparison sort for $n$ elements requires $\Omega(n \log n)$ comparisons because it must distinguish between $n!$ outcomes.