Sorting (Algorithms) | GATE CS Mastery

Cheat sheets

ALG-06Cheat sheet1 pageIn a paid pack

Insertion, Selection, Bubble and Inversions

Insertion, selection and bubble sort as code-level procedures, traced pass by pass on one array with every state, comparison and swap counted by script; exact best and worst counts; inversions and why insertion shifts and bubble swaps both equal the inversion count; the exact comparison count of insertion sort; the number of bubble passes; stability with a counterexample for selection sort; adaptivity, online behaviour and counts on sorted, reversed and equal inputs.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

ALG-07Cheat sheet1 pageIn a paid pack

Merge Sort and Quicksort

Merging two sorted lists with best and worst comparison counts; merge sort's exact worst-case count, number of merges, space and stability, with the solved GATE CS 2026 Set 2 Q.32; quicksort with the Lomuto partition traced step by step and the Hoare partition traced on the same array; pivot choices and the inputs that make quicksort quadratic, including equal keys; best, average and worst recurrences; the exact expected comparison count with a random pivot; unbalanced but constant splits; stack depth; quickselect.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

Diagrams from ALG-07

Lomuto partition of 7 2 9 4 3 8 6 5 with pivot 5 (last). Rows: start i=-1; j=1 swap gives 2 7 9 4 3 8 6 5, i=0; j=3 gives 2 4 9 7 3 8 6 5, i=1; j=4 gives 2 4 3 7 9 8 6 5, i=2; final swap places 5 at index 3: 2 4 3 5 9 8 6 7. — Lomuto partition: the region up to i holds keys at most the pivot. Source: sheet ALG-07.

ALG-08Cheat sheet1 pageIn a paid pack

Heap Sort, Linear-Time Sorts, Lower Bound

Heap sort as build-max-heap followed by n - 1 extractions, traced on five keys, with its cost, instability and in-place behaviour; counting sort traced with prefix sums and a right-to-left scan that keeps it stable; LSD radix sort traced digit by digit with its cost in digits and base; bucket sort with its uniform-input assumption and worst case; the decision-tree argument for the comparison lower bound with exact values of ceil(lg n!) for n up to 12, and which sorts escape it.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.

ALG-09Cheat sheet1 pageIn a paid pack

Sorting Master Comparison Table

A master table of bubble, selection, insertion, merge, quick, heap, counting, radix and bucket sort with best, average and worst time, extra space, stability, in-place and adaptive behaviour and the exact comparison or swap counts; a second table of measured comparison and swap counts for eight keys in sorted, reversed, all-equal and mixed order; recognition cues for choosing a sort; stability and in-place definitions; and commonly confused facts.

Partial preview

A partial preview of the top of the sheet. The full sheet is in the Algorithms cheat sheet pack.