Unit VII: Sorting (7 Hrs.)

Data Structures & Algorithms — Complete Detailed Chapter Notes

Every algorithm includes: detailed concept · pseudocode · step-form algorithm · two fully-traced examples (with tables) · best-case & worst-case walkthroughs · complete Java code · complexity analysis · advantages/disadvantages. Ends with fully-answered important questions.

Introduction
Internal & External Sort
Common Sorting Algorithms
Efficiency of Sorting & Big-O Notation
Important Questions with Full Answers

7.1 Introduction

Sorting is the process of rearranging a given collection of data elements into a specific logical order — either ascending (smallest → largest) or descending (largest → smallest). The attribute on which the order is decided is called the sort key (for example, sorting students by roll number, or sorting words alphabetically).

Why sorting is important

Sorting is one of the most studied operations in computer science because it appears as a building block almost everywhere:

Faster searching: Binary Search needs sorted data and runs in O(log n) instead of O(n).
Data presentation: Reports, leaderboards, contact lists, and search results all need ordered data.
Detecting duplicates / finding median: Both become trivial once data is sorted.
Efficiency of other algorithms: Many algorithms (e.g., Kruskal's MST) begin by sorting.

Important terminology

Term	Meaning
Sort key	The field used to decide the order (e.g., marks, name).
Comparison sort	A sort that orders elements by comparing pairs (all sorts in this unit).
In-place sort	Needs only O(1) extra memory beyond the input array (e.g., Bubble, Selection, Insertion).
Stable sort	Keeps the relative order of two elements that have equal keys (e.g., Merge, Insertion, Bubble).
Unstable sort	May reorder elements with equal keys (e.g., Quick, Selection, Shell).
Pass	One complete scan/iteration over (part of) the data.

Stability — a concrete picture

Suppose we sort records by marks only, and two students A(80) and B(80) appear in the input as [A(80), B(80)].

A stable sort keeps them as A, B in the output.
An unstable sort may output B, A. Stability matters when sorting by multiple keys (e.g., sort by name first, then by marks).

7.2 Internal & External Sort

Sorting techniques are classified by where the data lives during sorting.

Internal Sort

The entire dataset fits in main memory (RAM) and is sorted there.
Random access to any element is fast (RAM), so these algorithms freely jump around the array.
Examples: Bubble, Insertion, Selection, Quick, Merge (in-memory), Shell, Heap Sort.

External Sort

The dataset is too large to fit in RAM, so it is kept on secondary storage (hard disk, SSD, tape).
Data is brought into memory in chunks (called "runs"), each run is sorted internally, written back to disk, and finally all sorted runs are merged together.
Disk access is far slower than RAM, so external sorts are designed to use sequential disk reads/writes.
Example: External Merge Sort — used by databases to sort gigabytes/terabytes of records.

Detailed comparison

Feature	Internal Sort	External Sort
Data location	Main memory (RAM)	Secondary memory (disk/tape)
Data size	Small — fits in RAM	Very large — does not fit in RAM
Access pattern	Random access (fast)	Sequential access (avoids slow seeks)
Speed	Fast	Slower (limited by disk I/O)
Technique	Sort directly in memory	Create sorted runs, then merge runs
Typical example	Quick Sort, Merge Sort	External Merge Sort

How external merge sort works (overview): if we must sort 9 GB but have only 1 GB RAM, we read 1 GB at a time, sort it internally, and write 9 sorted "runs" to disk. Then we merge these 9 runs using a small in-memory buffer per run, repeatedly picking the smallest front element — producing the final sorted file with only sequential disk passes.

7.3 Common Sorting Algorithms

The next seven sections each cover one algorithm in full detail.

7.3.1 Bubble Sort

Concept (detailed)

Bubble Sort works by repeatedly comparing adjacent pairs of elements and swapping them whenever they are in the wrong order. After the first complete pass, the largest element has "bubbled up" to the last position. After the second pass, the second-largest is in its place, and so on. With each pass, the unsorted region shrinks by one from the right.

An optimized version uses a swapped flag: if a full pass makes no swaps, the array is already sorted and we stop early — this gives the O(n) best case.

Pseudocode

procedure BUBBLE_SORT(A, n)
    for i ← 0 to n-2 do
        swapped ← false
        for j ← 0 to n-2-i do
            if A[j] > A[j+1] then
                swap(A[j], A[j+1])
                swapped ← true
            end if
        end for
        if swapped = false then
            break              // already sorted
        end if
    end for
end procedure

Algorithm (step form)

Start with i = 0.
Set swapped = false.
Repeat for j from 0 to (n-2-i): if A[j] > A[j+1], swap them and set swapped = true.
After the inner loop, the largest unsorted element is now at the end.
If swapped is still false, the array is sorted → stop.
Increase i and repeat from step 2 until i = n-1.

Example 1 — sort `[5, 1, 4, 2, 8]` (ascending), n = 5

Pass 1 (i=0, j: 0→3):

j	Compare	Action	Array
0	5 > 1	swap	[1, 5, 4, 2, 8]
1	5 > 4	swap	[1, 4, 5, 2, 8]
2	5 > 2	swap	[1, 4, 2, 5, 8]
3	5 > 8? no	—	[1, 4, 2, 5, 8]

→ 8 is now fixed at the end.

Pass 2 (i=1, j: 0→2):

j	Compare	Action	Array
0	1 > 4? no	—	[1, 4, 2, 5, 8]
1	4 > 2	swap	[1, 2, 4, 5, 8]
2	4 > 5? no	—	[1, 2, 4, 5, 8]

Pass 3 (i=2, j: 0→1): compares 1,2 and 2,4 → no swaps → swapped = false → stop.

Sorted result: [1, 2, 4, 5, 8]

Example 2 — sort `[29, 10, 14, 37, 13]`, n = 5

Pass 1:

j	Compare	Action	Array
0	29 > 10	swap	[10, 29, 14, 37, 13]
1	29 > 14	swap	[10, 14, 29, 37, 13]
2	29 > 37? no	—	[10, 14, 29, 37, 13]
3	37 > 13	swap	[10, 14, 29, 13, 37]

→ 37 fixed.

Pass 2:

j	Compare	Action	Array
0	10 > 14? no	—	[10, 14, 29, 13, 37]
1	14 > 29? no	—	[10, 14, 29, 13, 37]
2	29 > 13	swap	[10, 14, 13, 29, 37]

Pass 3:

j	Compare	Action	Array
0	10 > 14? no	—	[10, 14, 13, 29, 37]
1	14 > 13	swap	[10, 13, 14, 29, 37]

Pass 4: compares 10,13 → no swap → stop.

Sorted result: [10, 13, 14, 29, 37]

Best Case — already sorted `[1, 2, 3, 4, 5]`

Pass 1 compares every adjacent pair: 1<2, 2<3, 3<4, 4<5 → no swap at all → swapped = false → algorithm stops after one pass.

Comparisons = n−1 = 4, swaps = 0 → Time = O(n).

Worst Case — reverse sorted `[5, 4, 3, 2, 1]`

Every comparison causes a swap.

Pass	Swaps performed	Array after pass
1	5↔4,5↔3,5↔2,5↔1 (4)	[4, 3, 2, 1, 5]
2	4↔3,4↔2,4↔1 (3)	[3, 2, 1, 4, 5]
3	3↔2,3↔1 (2)	[2, 1, 3, 4, 5]
4	2↔1 (1)	[1, 2, 3, 4, 5]

Total comparisons/swaps = 4+3+2+1 = 10 = n(n−1)/2 → Time = O(n²).

Java Code

public class BubbleSort {
    static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {        // adjacent pair out of order
                    int temp = arr[j];            // swap
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) break;                  // optimization: already sorted
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 1, 4, 2, 8};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // [1, 2, 4, 5, 8]
    }
}

Complexity

Case	Comparisons	Time	Space
Best (sorted)	n−1	O(n)	O(1)
Average	~n²/2	O(n²)	O(1)
Worst (reverse)	n(n−1)/2	O(n²)	O(1)

Stable: Yes · In-place: Yes.

Advantages & Disadvantages

Advantages: Very simple to understand/implement; stable; detects an already-sorted array in O(n); needs no extra memory.
Disadvantages: Very slow O(n²) for large data; performs many swaps; rarely used in practice except for teaching or tiny arrays.

7.3.2 Insertion Sort

Concept (detailed)

Insertion Sort builds the final sorted array one element at a time. It keeps the left part sorted and the right part unsorted. In each step it takes the first unsorted element (the key) and inserts it into its correct position within the sorted left part by shifting all larger elements one place to the right. This is exactly how most people sort a hand of playing cards.

Pseudocode

procedure INSERTION_SORT(A, n)
    for i ← 1 to n-1 do
        key ← A[i]
        j ← i - 1
        while j ≥ 0 and A[j] > key do
            A[j+1] ← A[j]      // shift right
            j ← j - 1
        end while
        A[j+1] ← key           // place key in the gap
    end for
end procedure

Algorithm (step form)

Treat A[0] as a sorted region of size 1.
For each i from 1 to n−1: store key = A[i].
Compare key with elements to its left; while a left element is greater than key, shift it one position right.
Place key into the empty slot created by shifting.
The sorted region grows by one; repeat until all elements are placed.

Example 1 — sort `[9, 5, 1, 4, 3]`, n = 5

i	key	Shifts (larger move right)	Array after insertion
1	5	9→	[5, 9, 1, 4, 3]
2	1	9→, 5→	[1, 5, 9, 4, 3]
3	4	9→, 5→ (1<4 stop)	[1, 4, 5, 9, 3]
4	3	9→, 5→, 4→ (1<3 stop)	[1, 3, 4, 5, 9]

Sorted result: [1, 3, 4, 5, 9]

Example 2 — sort `[12, 11, 13, 5, 6]`, n = 5

i	key	Shifts	Array after insertion
1	11	12→	[11, 12, 13, 5, 6]
2	13	none (12<13)	[11, 12, 13, 5, 6]
3	5	13→, 12→, 11→	[5, 11, 12, 13, 6]
4	6	13→, 12→, 11→ (5<6 stop)	[5, 6, 11, 12, 13]

Sorted result: [5, 6, 11, 12, 13]

Best Case — already sorted `[1, 2, 3, 4, 5]`

For every i, A[i-1] < key, so the while condition is immediately false → no shifting, just one comparison per element.

Comparisons = n−1, shifts = 0 → Time = O(n).

Worst Case — reverse sorted `[5, 4, 3, 2, 1]`

Each key must travel all the way to the front, shifting every sorted element.

i	key	Shifts	Array
1	4	5→ (1)	[4, 5, 3, 2, 1]
2	3	5→, 4→ (2)	[3, 4, 5, 2, 1]
3	2	5→, 4→, 3→ (3)	[2, 3, 4, 5, 1]
4	1	5→, 4→, 3→, 2→ (4)	[1, 2, 3, 4, 5]

Total shifts = 1+2+3+4 = 10 = n(n−1)/2 → Time = O(n²).

Java Code

public class InsertionSort {
    static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {   // shift larger elements right
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;                  // place key into the gap
        }
    }

    public static void main(String[] args) {
        int[] arr = {9, 5, 1, 4, 3};
        insertionSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // [1, 3, 4, 5, 9]
    }
}

Complexity

Case	Time	Space
Best (sorted)	O(n)	O(1)
Average	O(n²)	O(1)
Worst (reverse)	O(n²)	O(1)

Stable: Yes · In-place: Yes.

Advantages & Disadvantages

Advantages: Simple; stable; very efficient for small or nearly sorted arrays (close to O(n)); sorts the array as it receives data (online algorithm).
Disadvantages: O(n²) for large random data due to heavy shifting.

7.3.3 Selection Sort

Concept (detailed)

Selection Sort divides the array into a sorted left part and an unsorted right part. In each pass it selects the minimum element from the unsorted part and swaps it into the first position of the unsorted part. Thus after pass i, the first i+1 elements are the smallest i+1 elements in sorted order. It always makes exactly n−1 swaps — the fewest of the elementary sorts — which is useful when writes/swaps are expensive.

Pseudocode

procedure SELECTION_SORT(A, n)
    for i ← 0 to n-2 do
        minIndex ← i
        for j ← i+1 to n-1 do
            if A[j] < A[minIndex] then
                minIndex ← j
            end if
        end for
        swap(A[i], A[minIndex])
    end for
end procedure

Algorithm (step form)

For each position i from 0 to n−2: assume A[i] is the minimum (minIndex = i).
Scan the rest of the array (j from i+1 to n−1); whenever A[j] < A[minIndex], update minIndex = j.
Swap A[i] with A[minIndex] — placing the smallest unsorted element at position i.
Repeat until the whole array is sorted.

Example 1 — sort `[64, 25, 12, 22, 11]`, n = 5

i	Search range	Minimum found	Swap	Array
0	[64,25,12,22,11]	11 (idx 4)	64↔11	[11, 25, 12, 22, 64]
1	[25,12,22,64]	12 (idx 2)	25↔12	[11, 12, 25, 22, 64]
2	[25,22,64]	22 (idx 3)	25↔22	[11, 12, 22, 25, 64]
3	[25,64]	25 (idx 3)	none	[11, 12, 22, 25, 64]

Sorted result: [11, 12, 22, 25, 64]

Example 2 — sort `[29, 10, 14, 37, 13]`, n = 5

i	Search range	Minimum found	Swap	Array
0	[29,10,14,37,13]	10 (idx 1)	29↔10	[10, 29, 14, 37, 13]
1	[29,14,37,13]	13 (idx 4)	29↔13	[10, 13, 14, 37, 29]
2	[14,37,29]	14 (idx 2)	none	[10, 13, 14, 37, 29]
3	[37,29]	29 (idx 4)	37↔29	[10, 13, 14, 29, 37]

Sorted result: [10, 13, 14, 29, 37]

Best & Worst Case

Selection Sort always performs the same number of comparisons — the inner loop runs fully regardless of input — so:

Best case (already sorted): still scans everything → O(n²), but 0 useful swaps.
Worst case (reverse sorted): also O(n²). This makes its time insensitive to input order (always Θ(n²)), while keeping swaps at exactly n−1.

Java Code

public class SelectionSort {
    static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) minIndex = j;  // track smallest
            }
            int temp = arr[i];            // swap smallest into position i
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println(java.util.Arrays.toString(arr)); // [11, 12, 22, 25, 64]
    }
}

Complexity

Case	Time	Space
Best	O(n²)	O(1)
Average	O(n²)	O(1)
Worst	O(n²)	O(1)

Stable: No · In-place: Yes.

Advantages & Disadvantages

Advantages: Simple; minimum number of swaps (n−1) — good when writing to memory is costly (e.g., flash); in-place.
Disadvantages: Always O(n²) even if the data is already sorted; not stable.

7.3.4 Quick Sort

Concept (detailed)

Quick Sort is a Divide-and-Conquer algorithm. It works in three steps:

Divide: Choose a pivot element and partition the array so that all elements smaller than the pivot go to its left and all larger elements go to its right. After partitioning, the pivot is in its final sorted position.
Conquer: Recursively apply Quick Sort to the left sub-array and the right sub-array.
Combine: No explicit combine step is needed — the array is sorted in place once recursion completes.

We use the Lomuto partition scheme with the last element as pivot. The efficiency of Quick Sort depends heavily on pivot choice: a good pivot splits the array roughly in half (giving O(n log n)); a bad pivot (smallest/largest each time) gives unbalanced splits (O(n²)).

Pseudocode

procedure QUICK_SORT(A, low, high)
    if low < high then
        pi ← PARTITION(A, low, high)
        QUICK_SORT(A, low, pi - 1)
        QUICK_SORT(A, pi + 1, high)
    end if
end procedure

function PARTITION(A, low, high)        // Lomuto, pivot = A[high]
    pivot ← A[high]
    i ← low - 1
    for j ← low to high - 1 do
        if A[j] < pivot then
            i ← i + 1
            swap(A[i], A[j])
        end if
    end for
    swap(A[i+1], A[high])               // put pivot in its place
    return i + 1
end function

Algorithm (step form)

If low < high: pick pivot = A[high], set boundary i = low − 1.
Scan j from low to high−1; whenever A[j] < pivot, advance i and swap A[i] with A[j] (moves the smaller element to the left region).
Swap A[i+1] with the pivot A[high]; now the pivot sits at index i+1 in its final position; return i+1.
Recursively Quick Sort the left part [low, i] and the right part [i+2, high].

Example 1 — sort `[10, 80, 30, 90, 40, 50, 70]` (pivot = last)

Partition QS(0,6), pivot = 70, i starts at −1:

j	A[j] < 70 ?	i	swap	Array
0	10 yes	0	(0,0)	[10, 80, 30, 90, 40, 50, 70]
1	80 no	0	—	[10, 80, 30, 90, 40, 50, 70]
2	30 yes	1	(1,2)	[10, 30, 80, 90, 40, 50, 70]
3	90 no	1	—	[10, 30, 80, 90, 40, 50, 70]
4	40 yes	2	(2,4)	[10, 30, 40, 90, 80, 50, 70]
5	50 yes	3	(3,5)	[10, 30, 40, 50, 80, 90, 70]
place pivot	—	—	(4,6)	[10, 30, 40, 50, 70, 90, 80]

Pivot 70 is fixed at index 4. Now recurse:

Left QS(0,3) on [10,30,40,50], pivot 50 → places 50 at idx 3 → recurse [10,30,40] pivot 40 → places 40 → recurse [10,30] pivot 30 → [10,30]. Left fully sorted: [10,30,40,50].
Right QS(5,6) on [90,80], pivot 80 → 90 not < 80 → swap places 80 before 90 → [80,90].

Sorted result: [10, 30, 40, 50, 70, 80, 90]

Example 2 — sort `[8, 3, 1, 7, 0, 10, 2]` (pivot = last)

Partition QS(0,6), pivot = 2, i = −1:

j	A[j] < 2 ?	i	swap	Array
0	8 no	−1	—	[8, 3, 1, 7, 0, 10, 2]
1	3 no	−1	—	[8, 3, 1, 7, 0, 10, 2]
2	1 yes	0	(0,2)	[1, 3, 8, 7, 0, 10, 2]
3	7 no	0	—	[1, 3, 8, 7, 0, 10, 2]
4	0 yes	1	(1,4)	[1, 0, 8, 7, 3, 10, 2]
5	10 no	1	—	[1, 0, 8, 7, 3, 10, 2]
place pivot	—	—	(2,6)	[1, 0, 2, 7, 3, 10, 8]

Pivot 2 fixed at idx 2. Recurse:

Left QS(0,1) on [1,0], pivot 0 → swap → [0,1].
Right QS(3,6) on [7,3,10,8], pivot 8 → after partition places 8 → [7,3,8,10], then [7,3] pivot 3 → [3,7].

Sorted result: [0, 1, 2, 3, 7, 8, 10]

Best Case — balanced partitions

When the pivot always splits the array into two nearly equal halves (e.g., the pivot is the median), the recursion depth is log₂n and each level does O(n) work → Time = O(n log n). Illustration for n = 8: level 0 sorts 8, level 1 sorts 4+4, level 2 sorts 2+2+2+2, level 3 done → about log₂8 = 3 levels × O(n) = O(n log n).

Worst Case — already sorted input `[1, 2, 3, 4, 5]` with last-element pivot

Each partition picks the largest remaining element as pivot, producing one empty side and one side of size n−1:

Partition 1: pivot 5 → left size 4, right size 0
Partition 2: pivot 4 → left size 3
… and so on → n levels each costing O(n) → Time = O(n²). (Fix in practice: choose a random pivot or the median-of-three to avoid this.)

Java Code

public class QuickSort {
    static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = partition(arr, low, high);   // pivot's final index
            quickSort(arr, low, pi - 1);          // sort left part
            quickSort(arr, pi + 1, high);         // sort right part
        }
    }

    static int partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int t = arr[i]; arr[i] = arr[j]; arr[j] = t;   // swap smaller left
            }
        }
        int t = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = t; // pivot to place
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 80, 30, 90, 40, 50, 70};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(java.util.Arrays.toString(arr)); // [10, 30, 40, 50, 70, 80, 90]
    }
}

Complexity

Case	Time	Space (recursion)
Best	O(n log n)	O(log n)
Average	O(n log n)	O(log n)
Worst (sorted + bad pivot)	O(n²)	O(n)

Stable: No · In-place: Yes.

Advantages & Disadvantages

Advantages: Usually the fastest general-purpose in-memory sort; in-place (low memory); excellent cache performance.
Disadvantages: O(n²) worst case with poor pivots; not stable; recursive (stack overhead).

7.3.5 Merge Sort

Concept (detailed)

Merge Sort is a Divide-and-Conquer algorithm:

Divide: Split the array into two halves about the middle.
Conquer: Recursively sort each half.
Combine (Merge): Merge the two sorted halves into a single sorted array by repeatedly taking the smaller of the two front elements.

The recursion keeps splitting until sub-arrays of size 1 (already sorted), then merges upward. Merging is the key step: it is stable and runs in linear time for each level. Because the array is always split in half, Merge Sort guarantees O(n log n) in all cases, but it needs O(n) extra memory for the temporary arrays during merging.

Pseudocode

procedure MERGE_SORT(A, left, right)
    if left < right then
        mid ← (left + right) / 2
        MERGE_SORT(A, left, mid)
        MERGE_SORT(A, mid+1, right)
        MERGE(A, left, mid, right)
    end if
end procedure

procedure MERGE(A, left, mid, right)
    copy A[left..mid]   into L
    copy A[mid+1..right] into R
    i ← 0; j ← 0; k ← left
    while i < len(L) and j < len(R) do
        if L[i] ≤ R[j] then A[k] ← L[i]; i ← i+1
        else                A[k] ← R[j]; j ← j+1
        k ← k+1
    end while
    copy any remaining L into A
    copy any remaining R into A
end procedure

Algorithm (step form)

If the segment has more than one element, compute the midpoint mid.
Recursively sort the left half [left, mid] and right half [mid+1, right].
Merge: copy both halves into temporary arrays L and R.
Compare the front elements of L and R; copy the smaller back into A; advance that pointer.
When one temp array empties, copy the remainder of the other.
The segment [left, right] is now sorted.

Example 1 — sort `[38, 27, 43, 3, 9, 82, 10]`, n = 7

Divide phase:

            [38, 27, 43, 3, 9, 82, 10]
                /                 \
        [38, 27, 43, 3]        [9, 82, 10]
          /        \            /       \
     [38, 27]   [43, 3]      [9, 82]   [10]
      /   \      /   \        /   \
   [38] [27] [43]  [3]     [9]  [82]

Merge (combine) phase:

Merge step	Inputs	Output
1	[38] + [27]	[27, 38]
2	[43] + [3]	[3, 43]
3	[27,38] + [3,43]	[3, 27, 38, 43]
4	[9] + [82]	[9, 82]
5	[9,82] + [10]	[9, 10, 82]
6	[3,27,38,43] + [9,10,82]	[3, 9, 10, 27, 38, 43, 82]

Sorted result: [3, 9, 10, 27, 38, 43, 82]

Example 2 — sort `[12, 11, 13, 5, 6, 7]`, n = 6

Divide:

        [12, 11, 13, 5, 6, 7]
          /              \
   [12, 11, 13]        [5, 6, 7]
     /     \            /     \
 [12,11]  [13]      [5,6]    [7]
  /  \                /  \
[12] [11]          [5]  [6]

Merge:

Merge step	Inputs	Output
1	[12] + [11]	[11, 12]
2	[11,12] + [13]	[11, 12, 13]
3	[5] + [6]	[5, 6]
4	[5,6] + [7]	[5, 6, 7]
5	[11,12,13] + [5,6,7]	[5, 6, 7, 11, 12, 13]

Sorted result: [5, 6, 7, 11, 12, 13]

Best & Worst Case

Merge Sort always divides into two equal halves (log n levels) and merges in O(n) per level, regardless of input order:

Best case (already sorted): still O(n log n) — it cannot finish early because it always recurses fully.
Worst case (reverse sorted): also O(n log n). So Merge Sort is Θ(n log n) — its biggest strength is this guaranteed performance.

Java Code

public class MergeSort {
    static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }

    static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1, n2 = right - mid;
        int[] L = new int[n1], R = new int[n2];
        for (int i = 0; i < n1; i++) L[i] = arr[left + i];
        for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

        int i = 0, j = 0, k = left;
        while (i < n1 && j < n2)
            arr[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];  // take smaller front
        while (i < n1) arr[k++] = L[i++];                 // remaining left
        while (j < n2) arr[k++] = R[j++];                 // remaining right
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println(java.util.Arrays.toString(arr)); // [3, 9, 10, 27, 38, 43, 82]
    }
}

Complexity

Case	Time	Space
Best	O(n log n)	O(n)
Average	O(n log n)	O(n)
Worst	O(n log n)	O(n)

Stable: Yes · In-place: No (needs O(n) extra).

Advantages & Disadvantages

Advantages: Guaranteed O(n log n) for all inputs; stable; ideal for linked lists and external sorting; predictable performance.
Disadvantages: Needs O(n) extra memory; slower than Quick Sort in practice for in-memory arrays due to copying.

7.3.6 Shell Sort

Concept (detailed)

Shell Sort is a generalization of Insertion Sort that allows the exchange of elements that are far apart. Plain Insertion Sort moves elements only one position at a time, so an element far from its correct place needs many shifts. Shell Sort first sorts elements that are a large gap apart, then progressively reduces the gap. When the gap finally becomes 1, the array is already nearly sorted, so the final insertion-sort pass is very fast.

The sequence of gaps is the gap sequence. The simplest (Shell's original) is gap = n/2, n/4, …, 1. Better sequences (Knuth, Hibbard) improve performance.

Pseudocode

procedure SHELL_SORT(A, n)
    gap ← n / 2
    while gap > 0 do
        for i ← gap to n-1 do
            temp ← A[i]
            j ← i
            while j ≥ gap and A[j-gap] > temp do
                A[j] ← A[j-gap]
                j ← j - gap
            end while
            A[j] ← temp
        end for
        gap ← gap / 2
    end while
end procedure

Algorithm (step form)

Start with gap = n/2.
Perform a gapped insertion sort: for each i from gap to n−1, compare A[i] with A[i−gap], A[i−2·gap], …, shifting larger elements forward by gap, and insert the element in the right gapped position.
Halve the gap (gap = gap/2) and repeat step 2.
When gap = 1, the final pass is ordinary insertion sort on a nearly-sorted array.

Example 1 — sort `[23, 29, 15, 19, 31, 7, 9, 5, 2]`, n = 9

Gap = 4 (compare elements 4 apart):

i	temp	Comparison / shift	Array
4	31	A[0]=23 < 31 → stay	[23, 29, 15, 19, 31, 7, 9, 5, 2]
5	7	A[1]=29 > 7 → shift; place at idx1	[23, 7, 15, 19, 31, 29, 9, 5, 2]
6	9	A[2]=15 > 9 → shift; place at idx2	[23, 7, 9, 19, 31, 29, 15, 5, 2]
7	5	A[3]=19 > 5 → shift; place at idx3	[23, 7, 9, 5, 31, 29, 15, 19, 2]
8	2	A[4]=31>2 shift, A[0]=23>2 shift; place at idx0	[2, 7, 9, 5, 23, 29, 15, 19, 31]

After gap 4: [2, 7, 9, 5, 23, 29, 15, 19, 31]

Gap = 2:

i	temp	Shift	Array
2	9	A[0]=2<9 stay	[2, 7, 9, 5, 23, 29, 15, 19, 31]
3	5	A[1]=7>5 shift; place idx1	[2, 5, 9, 7, 23, 29, 15, 19, 31]
4	23	A[2]=9<23 stay	(same)
5	29	A[3]=7<29 stay	(same)
6	15	A[4]=23>15 shift, A[2]=9<15 stop; place idx4	[2, 5, 9, 7, 15, 29, 23, 19, 31]
7	19	A[5]=29>19 shift, A[3]=7<19 stop; place idx5	[2, 5, 9, 7, 15, 19, 23, 29, 31]
8	31	A[6]=23<31 stay	(same)

After gap 2: [2, 5, 9, 7, 15, 19, 23, 29, 31]

Gap = 1 (ordinary insertion sort, nearly sorted): only 7 needs to move left past 9 → [2, 5, 7, 9, 15, 19, 23, 29, 31]

Sorted result: [2, 5, 7, 9, 15, 19, 23, 29, 31]

Example 2 — sort `[12, 34, 54, 2, 3]`, n = 5

Gap = 2:

i	temp	Shift	Array
2	54	A[0]=12<54 stay	[12, 34, 54, 2, 3]
3	2	A[1]=34>2 shift; place idx1	[12, 2, 54, 34, 3]
4	3	A[2]=54>3 shift, A[0]=12>3 shift; place idx0	[3, 2, 12, 34, 54]

After gap 2: [3, 2, 12, 34, 54]

Gap = 1: insert 2 before 3 → [2, 3, 12, 34, 54]

Sorted result: [2, 3, 12, 34, 54]

Best & Worst Case

Best case (already sorted): each gapped pass finds elements in order, only comparisons, no shifts → about O(n log n).
Worst case: depends on the gap sequence; with Shell's original n/2 sequence it can be O(n²), but with better sequences (Knuth: 3k+1) it improves to roughly O(n^1.5). Shell Sort's average is commonly cited as around O(n^1.25)–O(n^1.5).

Java Code

public class ShellSort {
    static void shellSort(int[] arr) {
        int n = arr.length;
        for (int gap = n / 2; gap > 0; gap /= 2) {        // shrink the gap
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) { // gapped insertion
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {23, 29, 15, 19, 31, 7, 9, 5, 2};
        shellSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
        // [2, 5, 7, 9, 15, 19, 23, 29, 31]
    }
}

Complexity

Case	Time	Space
Best	O(n log n)	O(1)
Average	≈ O(n^1.25) – O(n^1.5)	O(1)
Worst	O(n²) (original gaps)	O(1)

Stable: No · In-place: Yes.

Advantages & Disadvantages

Advantages: Much faster than plain Insertion Sort for medium arrays; in-place (no extra memory); simple to implement.
Disadvantages: Not stable; performance depends on the chosen gap sequence; analysis is complex.

7.3.7 Binary (Tree) Sort

Concept (detailed)

Binary (Tree) Sort uses a Binary Search Tree (BST). The algorithm has two phases:

Build phase: Insert every element of the array into a BST. In a BST, for every node, all values in the left subtree are smaller and all values in the right subtree are larger.
Extract phase: Perform an in-order traversal (Left → Root → Right) of the BST. Because of the BST ordering property, in-order traversal visits the nodes in ascending sorted order.

Note: "Binary Sort" sometimes refers to Binary Insertion Sort (Insertion Sort that uses binary search to find the insertion point). The widely taught meaning in DSA courses is Binary Tree Sort, presented here; the binary-insertion variant is noted at the end.

Pseudocode

procedure BINARY_TREE_SORT(A, n)
    root ← NULL
    for each value v in A do
        root ← INSERT(root, v)
    end for
    INORDER(root)              // outputs sorted order
end procedure

function INSERT(node, v)
    if node = NULL then return new Node(v)
    if v < node.data then node.left  ← INSERT(node.left, v)
    else                 node.right ← INSERT(node.right, v)
    return node
end function

procedure INORDER(node)
    if node ≠ NULL then
        INORDER(node.left)
        visit(node.data)
        INORDER(node.right)
    end if
end procedure

Algorithm (step form)

Start with an empty BST (root = NULL).
For each array element, insert it: go left if smaller than the current node, right if larger, until an empty spot is found.
After all insertions, do an in-order traversal: recursively visit the left subtree, output the node, then visit the right subtree.
The sequence produced by in-order traversal is the sorted array.

Example 1 — sort `[45, 10, 7, 90, 12, 50, 30]`

Build BST (insert in order):

Insert	Placement
45	root
10	10<45 → left of 45
7	7<45→left, 7<10→left of 10
90	90>45 → right of 45
12	12<45→left, 12>10→right of 10
50	50>45→right, 50<90→left of 90
30	30<45→left, 30>10→right, 30>12→right of 12

Resulting BST:

In-order traversal (Left, Root, Right): 7 → 10 → 12 → 30 → 45 → 50 → 90

Sorted result: [7, 10, 12, 30, 45, 50, 90]

Example 2 — sort `[5, 2, 9, 1, 6]`

Build BST:

Insert	Placement
5	root
2	left of 5
9	right of 5
1	left of 2
6	6>5→right, 6<9→left of 9

Resulting BST:

In-order traversal: 1 → 2 → 5 → 6 → 9

Sorted result: [1, 2, 5, 6, 9]

Best Case — balanced tree

When insertions produce a balanced BST (height ≈ log n), each insertion costs O(log n) and traversal is O(n) → Time = O(n log n).

Worst Case — already sorted input `[1, 2, 3, 4, 5]`

Each new value is larger than all previous, so it always goes right, producing a skewed (linked-list-like) tree:

Insertion of the k-th element costs O(k), so total build time = 1+2+…+n = n(n−1)/2 → Time = O(n²). (Self-balancing trees like AVL/Red-Black fix this to guaranteed O(n log n).)

Java Code

import java.util.*;

public class BinaryTreeSort {
    static class Node {
        int data; Node left, right;
        Node(int data) { this.data = data; }
    }

    static Node insert(Node root, int value) {
        if (root == null) return new Node(value);
        if (value < root.data) root.left = insert(root.left, value);
        else root.right = insert(root.right, value);
        return root;
    }

    static void inorder(Node root, List<Integer> out) {
        if (root != null) {
            inorder(root.left, out);
            out.add(root.data);          // visit in sorted order
            inorder(root.right, out);
        }
    }

    static int[] binaryTreeSort(int[] arr) {
        Node root = null;
        for (int v : arr) root = insert(root, v);   // build BST
        List<Integer> out = new ArrayList<>();
        inorder(root, out);                         // in-order = sorted
        return out.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        int[] arr = {45, 10, 7, 90, 12, 50, 30};
        System.out.println(Arrays.toString(binaryTreeSort(arr)));
        // [7, 10, 12, 30, 45, 50, 90]
    }
}

Complexity

Case	Time	Space
Best / Average (balanced)	O(n log n)	O(n)
Worst (skewed, sorted input)	O(n²)	O(n)

Stable: No (basic version) · In-place: No (uses tree nodes).

Advantages & Disadvantages

Advantages: Naturally produces sorted output via in-order traversal; the same BST also supports fast search/insert/delete afterward; good average performance with balanced trees.
Disadvantages: O(n²) for sorted/skewed input unless self-balancing; needs extra memory for tree nodes/pointers; not in-place.

7.4 Efficiency of Sorting and Big-O Notation

What Big-O means

Big-O notation expresses the upper bound on the growth of an algorithm's running time as the input size n grows large. It ignores constant factors and lower-order terms, focusing only on the dominant growth rate. For example, T(n) = 3n² + 5n + 100 is O(n²) because, for large n, the n² term dominates.

Big-O lets us compare algorithms independent of hardware, language, or compiler, by answering: "How does the work scale as the data gets bigger?"

Ordering of common growth rates (slow-growing → fast-growing)

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

Growth	Name	Sorting example
O(n)	Linear	Best case of Bubble/Insertion
O(n log n)	Linearithmic	Merge, Quick (avg), Heap
O(n²)	Quadratic	Bubble, Insertion, Selection (worst)

Master comparison table of all sorts in this unit

Algorithm	Best	Average	Worst	Space	Stable	In-place	Method
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Exchange
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)	Yes	Yes	Insertion
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)	No	Yes	Selection
Quick Sort	O(n log n)	O(n log n)	O(n²)	O(log n)	No	Yes	Divide & Conquer
Merge Sort	O(n log n)	O(n log n)	O(n log n)	O(n)	Yes	No	Divide & Conquer
Shell Sort	O(n log n)	~O(n^1.25)	O(n²)	O(1)	No	Yes	Insertion (gapped)
Binary Tree Sort	O(n log n)	O(n log n)	O(n²)	O(n)	No	No	Tree (BST)

How to choose a sorting algorithm

Small or nearly-sorted data: Insertion Sort (close to O(n)).
General-purpose, fastest in memory: Quick Sort.
Need guaranteed O(n log n) and/or stability: Merge Sort (also best for linked lists).
Huge data that does not fit in RAM: External Merge Sort.
Writes/swaps are expensive (e.g., flash memory): Selection Sort (only n−1 swaps).
Medium data, no extra memory, simple code: Shell Sort.

Important Questions with Full Answers

Short Questions (2 marks each)

Q1. Define sorting and state why it is important. Sorting is the process of arranging data elements into a specific order (ascending or descending) based on a sort key. It is important because it makes searching faster (e.g., binary search needs sorted data), helps present data meaningfully (reports, rankings), simplifies tasks like finding duplicates or the median, and serves as a preprocessing step for many other algorithms.

Q2. Differentiate between internal and external sorting. Internal sorting is used when the entire dataset fits in main memory (RAM) and is sorted directly there with fast random access — examples are Quick Sort and Bubble Sort. External sorting is used when data is too large for RAM and must reside on disk; the data is sorted in chunks called runs, written back, and then merged using sequential disk access — the main example is External Merge Sort.

Q3. What is a stable sorting algorithm? Give two examples. A stable sort preserves the relative order of elements that have equal keys. For example, if two records have the same key and appear in the order A then B in the input, a stable sort keeps them as A then B in the output. Examples: Merge Sort and Insertion Sort (also Bubble Sort).

Q4. Why is the best case of Bubble Sort O(n)? With the swapped-flag optimization, if the array is already sorted, the first pass compares all adjacent pairs and performs no swaps. Since swapped remains false, the algorithm stops after that single pass of n−1 comparisons, giving O(n).

Q5. Why does Quick Sort degrade to O(n²) in the worst case? When the chosen pivot is always the smallest or largest element (for instance, an already-sorted array with the last element as pivot), each partition splits the array into one empty part and one part of size n−1. This creates n levels of recursion, each doing O(n) work, giving O(n²). Choosing a random or median-of-three pivot avoids this.

Q6. Which sorting algorithm makes the fewest swaps, and why is that useful? Selection Sort makes the fewest swaps — at most n−1, one per pass. This is useful when writing to memory is expensive (such as flash storage or EEPROM), because it minimizes the number of write operations even though it still does O(n²) comparisons.

Q7. State the advantage of Shell Sort over Insertion Sort. Shell Sort compares and moves elements that are far apart using a gap, so out-of-place elements travel large distances quickly instead of shifting one step at a time. By the time the gap becomes 1, the array is nearly sorted, so the final insertion pass does very little work — making Shell Sort much faster than plain Insertion Sort on medium-sized arrays.

Q8. Why is Merge Sort preferred for sorting linked lists and external data? Merge Sort accesses data sequentially during merging and does not require random access, which suits linked lists (no index needed) and external storage (sequential disk reads/writes are fast). It also guarantees O(n log n) regardless of input order and is stable.

Long Questions (6–10 marks each)

Q1. Explain Quick Sort in detail with its algorithm, a complete trace, and complexity analysis.

Quick Sort is a divide-and-conquer algorithm. It selects a pivot, partitions the array so smaller elements lie to its left and larger to its right (placing the pivot in its final position), and then recursively sorts the two partitions.

Partition algorithm (Lomuto, pivot = last element): set i = low − 1; for each j from low to high−1, if A[j] < pivot, increment i and swap A[i] with A[j]; finally swap A[i+1] with the pivot and return i+1.

Trace on [10, 80, 30, 90, 40, 50, 70] with pivot 70: scanning left to right, 10 and 30 and 40 and 50 are moved to the left region, giving [10, 30, 40, 50, 70, 90, 80] with 70 fixed at index 4. The left sub-array [10,30,40,50] and right sub-array [90,80] are then sorted recursively, producing the final sorted array [10, 30, 40, 50, 70, 80, 90].

Complexity: When pivots split the array evenly, the recursion depth is log n and each level costs O(n), giving O(n log n) in the best and average cases. When pivots are consistently the smallest or largest element (e.g., a sorted array), partitions are maximally unbalanced, giving n levels of O(n) work and O(n²) in the worst case. Space is O(log n) for the recursion stack. Quick Sort is in-place but not stable, and is usually the fastest general-purpose in-memory sort.

Q2. Compare Bubble Sort, Selection Sort, and Insertion Sort with respect to time complexity, stability, number of swaps, and suitable use cases.

Aspect	Bubble Sort	Selection Sort	Insertion Sort
Best-case time	O(n)	O(n²)	O(n)
Average/Worst time	O(n²)	O(n²)	O(n²)
Stability	Stable	Unstable	Stable
Number of swaps	Many (up to n²/2)	Few (n−1)	Moderate (shifts)
Sensitive to input order	Yes (early stop)	No (always same work)	Yes (fast if nearly sorted)
Best use case	Teaching / tiny data	When swaps are costly	Small or nearly sorted data

All three are simple, in-place, O(n²) comparison sorts suitable only for small datasets. Bubble and Insertion Sort can finish in O(n) on already-sorted input, while Selection Sort always performs Θ(n²) comparisons but guarantees the minimum number of swaps. Insertion Sort is generally the most practical of the three because it is fast on nearly-sorted data and is stable.

Q3. Explain Merge Sort with its algorithm, a full trace, and state why it guarantees O(n log n). Why is it suited to external sorting?

Merge Sort is a divide-and-conquer algorithm: divide the array into two halves, recursively sort each half, and merge the two sorted halves into one sorted array by repeatedly taking the smaller of the two front elements.

Trace on [38, 27, 43, 3, 9, 82, 10]: the array is split down to single elements, then merged upward — [38],[27]→[27,38]; [43],[3]→[3,43]; these merge to [3,27,38,43]; on the right [9,82] and [10] merge to [9,10,82]; finally [3,27,38,43] and [9,10,82] merge to [3, 9, 10, 27, 38, 43, 82].

Why O(n log n) is guaranteed: the array is always split exactly in half, so there are about log₂n levels of recursion. At each level, the merge steps together process all n elements in O(n) time. Therefore total time is O(n) × O(log n) = O(n log n) in the best, average, and worst cases — performance does not depend on input order.

Why it suits external sorting: when data is too large for memory, Merge Sort's structure maps directly onto creating sorted runs and merging them with sequential disk access. It never needs random access, which is exactly what slow secondary storage favors; it is also stable and predictable.

Q4. What is Shell Sort? Explain how the gap sequence improves Insertion Sort, give a full trace, and discuss its complexity.

Shell Sort is an improved Insertion Sort that compares elements separated by a gap rather than only adjacent elements. Sorting distant elements first removes large-scale disorder quickly; as the gap shrinks to 1, the array becomes nearly sorted, so the final insertion pass does minimal work.

Trace on [23, 29, 15, 19, 31, 7, 9, 5, 2] (n=9): With gap = 4, sub-sequences four apart are sorted, giving [2, 7, 9, 5, 23, 29, 15, 19, 31]. With gap = 2, the array becomes [2, 5, 9, 7, 15, 19, 23, 29, 31]. With gap = 1, only 7 and 9 are swapped, yielding the sorted array [2, 5, 7, 9, 15, 19, 23, 29, 31].

Complexity: the best case is about O(n log n); the worst case is O(n²) with the original n/2 gap sequence but improves to roughly O(n^1.5) with better sequences (such as Knuth's 3k+1). Shell Sort is in-place (O(1) extra space) but not stable. Its advantage over plain Insertion Sort is far fewer total shifts on medium-sized arrays.

Q5. Explain Binary (Tree) Sort with a complete example and its best/worst-case complexity.

Binary Tree Sort works in two phases. First, every element is inserted into a Binary Search Tree (BST), where smaller values go left and larger values go right. Second, an in-order traversal (Left → Root → Right) of the BST outputs the elements in ascending sorted order, because that is the defining property of a BST.

Example on [45, 10, 7, 90, 12, 50, 30]: inserting these builds a BST with 45 at the root, 10 and 90 as its children, and so on; an in-order traversal then visits 7, 10, 12, 30, 45, 50, 90, which is the sorted output.

Complexity: if insertions produce a balanced tree (height ≈ log n), each insert costs O(log n) and traversal is O(n), giving O(n log n). If the input is already sorted, every element goes to the same side, producing a skewed tree shaped like a linked list; the k-th insertion then costs O(k) and the total becomes 1+2+…+n = O(n²). Using a self-balancing BST (AVL or Red-Black tree) keeps the height logarithmic and guarantees O(n log n). The basic version is not in-place (it needs tree nodes) and is not stable.

Q6. Explain Big-O notation. Compare all major sorting algorithms by best, average, and worst-case time complexity, and explain how to choose among them.

Big-O notation describes the upper bound on how an algorithm's running time grows as the input size n increases, ignoring constants and lower-order terms and keeping only the dominant term. For example, an algorithm taking 3n² + 5n + 100 operations is O(n²). It allows hardware-independent comparison of scalability, with common rates ordered as O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ).

Algorithm	Best	Average	Worst	Stable	In-place
Bubble	O(n)	O(n²)	O(n²)	Yes	Yes
Insertion	O(n)	O(n²)	O(n²)	Yes	Yes
Selection	O(n²)	O(n²)	O(n²)	No	Yes
Quick	O(n log n)	O(n log n)	O(n²)	No	Yes
Merge	O(n log n)	O(n log n)	O(n log n)	Yes	No
Shell	O(n log n)	~O(n^1.25)	O(n²)	No	Yes
Binary Tree	O(n log n)	O(n log n)	O(n²)	No	No

Choosing: use Insertion Sort for small or nearly-sorted data; Quick Sort for fastest general in-memory sorting; Merge Sort when guaranteed O(n log n), stability, or linked-list/external sorting is needed; Selection Sort when minimizing swaps matters; and External Merge Sort when the data does not fit in memory.

LAB EXPERIMENT — UNIT V (LINKED LIST)

Title: Implementation and Performance Analysis of Sorting Algorithms Objective: Design and implement a menu-driven program to perform sorting using Bubble Sort, Insertion Sort, Selection Sort, Quick Sort, Merge Sort, Shell Sort, and Binary (Binary Insertion) Sort on a given dataset. Compare the sorted results, analyze the time complexity (Best, Average, and Worst Case) of each algorithm using Big O notation, and identify the most suitable algorithm for different data sizes. Additionally, explain the difference between Internal Sorting and External Sorting, write the algorithms for each sorting technique, and compare their efficiency and practical applications.

End of Unit VII — Sorting.

Part - 7 Sorting , Data Structure and Algorithm

Unit VII: Sorting (7 Hrs.)

Table of Contents

7.1 Introduction

Why sorting is important

Important terminology

Stability — a concrete picture

7.2 Internal & External Sort

Internal Sort

External Sort

Detailed comparison

7.3 Common Sorting Algorithms

7.3.1 Bubble Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [5, 1, 4, 2, 8] (ascending), n = 5

Example 2 — sort [29, 10, 14, 37, 13], n = 5

Best Case — already sorted [1, 2, 3, 4, 5]

Worst Case — reverse sorted [5, 4, 3, 2, 1]

Java Code

Complexity

Advantages & Disadvantages

7.3.2 Insertion Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [9, 5, 1, 4, 3], n = 5

Example 2 — sort [12, 11, 13, 5, 6], n = 5

Best Case — already sorted [1, 2, 3, 4, 5]

Worst Case — reverse sorted [5, 4, 3, 2, 1]

Java Code

Complexity

Advantages & Disadvantages

7.3.3 Selection Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [64, 25, 12, 22, 11], n = 5

Example 2 — sort [29, 10, 14, 37, 13], n = 5

Best & Worst Case

Java Code

Complexity

Advantages & Disadvantages

7.3.4 Quick Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [10, 80, 30, 90, 40, 50, 70] (pivot = last)

Example 2 — sort [8, 3, 1, 7, 0, 10, 2] (pivot = last)

Best Case — balanced partitions

Worst Case — already sorted input [1, 2, 3, 4, 5] with last-element pivot

Java Code

Complexity

Advantages & Disadvantages

7.3.5 Merge Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [38, 27, 43, 3, 9, 82, 10], n = 7

Example 2 — sort [12, 11, 13, 5, 6, 7], n = 6

Best & Worst Case

Java Code

Complexity

Advantages & Disadvantages

7.3.6 Shell Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [23, 29, 15, 19, 31, 7, 9, 5, 2], n = 9

Example 2 — sort [12, 34, 54, 2, 3], n = 5

Best & Worst Case

Java Code

Complexity

Advantages & Disadvantages

7.3.7 Binary (Tree) Sort

Concept (detailed)

Pseudocode

Algorithm (step form)

Example 1 — sort [45, 10, 7, 90, 12, 50, 30]

Example 1 — sort `[5, 1, 4, 2, 8]` (ascending), n = 5

Example 2 — sort `[29, 10, 14, 37, 13]`, n = 5

Best Case — already sorted `[1, 2, 3, 4, 5]`

Worst Case — reverse sorted `[5, 4, 3, 2, 1]`

Example 1 — sort `[9, 5, 1, 4, 3]`, n = 5

Example 2 — sort `[12, 11, 13, 5, 6]`, n = 5

Best Case — already sorted `[1, 2, 3, 4, 5]`

Worst Case — reverse sorted `[5, 4, 3, 2, 1]`

Example 1 — sort `[64, 25, 12, 22, 11]`, n = 5

Example 2 — sort `[29, 10, 14, 37, 13]`, n = 5

Example 1 — sort `[10, 80, 30, 90, 40, 50, 70]` (pivot = last)

Example 2 — sort `[8, 3, 1, 7, 0, 10, 2]` (pivot = last)

Worst Case — already sorted input `[1, 2, 3, 4, 5]` with last-element pivot

Example 1 — sort `[38, 27, 43, 3, 9, 82, 10]`, n = 7

Example 2 — sort `[12, 11, 13, 5, 6, 7]`, n = 6

Example 1 — sort `[23, 29, 15, 19, 31, 7, 9, 5, 2]`, n = 9

Example 2 — sort `[12, 34, 54, 2, 3]`, n = 5

Example 1 — sort `[45, 10, 7, 90, 12, 50, 30]`

Example 2 — sort `[5, 2, 9, 1, 6]`

Worst Case — already sorted input `[1, 2, 3, 4, 5]`