Insertion sort and inversions; stable and in-place sorting

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Bubble sort swaps equal what? from Lesson 3.1.1
• Selection sort comparisons on n elements? from Lesson 3.1.1
• Average-case analysis needs what? from Lesson 1.3.1

1 · The Hook

🎣

Card players sort a hand by picking up cards one at a time and sliding each into place among the cards already held. That is insertion sort. It is quadratic on random data, but almost linear on nearly sorted data, which is why real libraries use it for small or almost-sorted pieces. Its cost is measured exactly by inversions.

2 · Predict First

🤔

How many pairs (i, j) with i < j and A[i] > A[j] does A = [5, 2, 9, 1, 7, 3] have?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

5 > 2, 1, 3 (3 pairs); 2 > 1 (1); 9 > 1, 7, 3 (3); 7 > 3 (1). Total 8 inversions.

Insertion sort

for (i = 1; i < n; i++) {
    key = A[i]; j = i - 1;
    while (j >= 0 && A[j] > key) { A[j + 1] = A[j]; j--; }   // shift right
    A[j + 1] = key;
}

After step i, A[0..i] is sorted (it holds the original first i + 1 elements, in order).

Inversions

An inversion is a pair i < j with A[i] > A[j].

• Sorted array: 0; reverse-sorted: n(n − 1)/2; random: n(n − 1)/4 on average.
• Insertion sort makes exactly one shift per inversion: shifts = inversions.
• Comparisons lie between inversions and inversions + (n − 1).
• Running time Θ(n + I), where I = number of inversions: best Θ(n) (sorted), worst Θ(n²) (reversed), average Θ(n²).
• Binary insertion sort finds the place with binary search: O(n log n) comparisons, but still Θ(n²) shifts.

Trace on A = [5, 2, 9, 1, 7, 3]

Total shifts 8 = inversions.

Stable and in-place

• Stable: equal keys keep their original relative order. Matters when sorting records by one field after another. Stable: insertion, bubble, merge sort, counting sort. Not stable: selection, quicksort, heapsort.
• In-place: O(1) extra memory (beyond the array). In-place: bubble, selection, insertion, heapsort, quicksort (O(log n) stack). Not in-place: merge sort (Θ(n) buffer), counting sort.

4 · Visual

Insertion sort step i = 3: key = 1, sorted prefix [2, 5, 9]

[2, 5, 9 | 1, 7, 3]    9 > 1 shift, 5 > 1 shift, 2 > 1 shift, j = -1
[1, 2, 5, 9 | 7, 3]    3 shifts = the 3 inversions (2,1) (5,1) (9,1)

5 · Worked Examples

Example 1 Easy

Number of inversions in [4, 3, 2, 1]?

Solution

4 × 3 / 2 = 6.

Example 2 Medium

Insertion sort on [1, 3, 5, 7, 2, 4, 6, 8]: how many shifts?

Solution

Inversions: 3 > 2; 5 > 2, 4; 7 > 2, 4, 6 → 6 shifts.

Example 3 GATE

Insertion sort on an array of n elements where every element is at most 2 positions from its sorted place. Running time?

Solution

Each element has O(1) inversions, so I = O(n) → Θ(n).

6 · GATE Traps

⚠️

• Shifts = inversions exactly; comparisons are slightly more.
• Binary insertion sort cuts comparisons, not data movement.
• Stable ≠ in-place: merge sort is stable but not in-place; heapsort is in-place but not stable.
• Reverse-sorted input is insertion sort's worst case.

7 · Memory Hook

🧠

"One shift per inversion." Insertion sort costs n plus the disorder.

8 · Connect the Dots

Chapter 3.1 is complete: three Θ(n²) sorts and the inversion measure. Chapter 3.2 breaks the n² barrier with divide and conquer: merge sort first.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markInversions

Number of inversions in [3, 1, 4, 1, 5, 9, 2, 6]?

Numerical answer: ________

Q2MCQ1 markAfter two steps

Insertion sort on [5, 2, 9, 1, 7, 3]. Array after inserting the 4th element (i = 3)?

• (A) [1, 2, 5, 9, 7, 3]
• (B) [2, 5, 9, 1, 7, 3]
• (C) [2, 1, 5, 9, 7, 3]
• (D) [1, 2, 5, 7, 9, 3]

Q3NAT2 marksWorst-case shifts

Insertion sort on a reverse-sorted array of 12 elements. Number of shifts?

Numerical answer: ________

Q4MSQ2 marksStability

Which of these sorts are stable in their standard form?

• (A) Merge sort
• (B) Heapsort
• (C) Bubble sort
• (D) Insertion sort

Q5MCQ1 markNearly sorted

For an array with only O(n) inversions, insertion sort runs in:

• (A) Θ(n)
• (B) Θ(log n)
• (C) Θ(n²)
• (D) Θ(n log n)

10 · Rule Card

• Insertion: insert A[i] into sorted prefix by shifting. Shifts = inversions; Θ(n + I).
• Best Θ(n) (sorted), worst Θ(n²) (reverse, I = n(n−1)/2), average n²/4.
• Binary insertion: O(n log n) comparisons, Θ(n²) shifts.
• Stable: insertion, bubble, merge, counting. In-place: bubble, selection, insertion, heap, quick.

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

insertion sortinversionΘ(n + I) running timebinary insertion sortstable sortingin-place sorting

12 · Answer Vault