UNIT 7: SORTING TECHNIQUES

Interactive tutorial and algorithm playground

0

Introduction

1

Selection Sort

2

Insertion Sort

3

Quick Sort

4

Merge Sort

5

Heap Sort

6

Shell Sort

7

Algorithm Comparison

Introduction to Sorting

What is Sorting?

Sorting is the process of arranging data in a particular order (ascending or descending). Sorting algorithms specify the method to rearrange data efficiently.

Categories of Sorting

  • Internal Sorting: All data fits into main memory (RAM).
  • External Sorting: Data is too large for memory — uses disk storage.
  • Stable Sorting: Preserves relative order of equal elements.
  • In-Place Sorting: Uses $O(1)$ extra space only.
  • Adaptive Sorting: Runs faster if input is partially sorted.

7.1 Selection Sort: Concept & Complexity

Concept

Selection sort is an in-place comparison algorithm. The list is divided into two parts: sorted (left) and unsorted (right). The smallest element is selected from the unsorted part and swapped with the leftmost element of the unsorted part.

Complexity Analysis

Case / MetricComplexityDescription
Time Complexity (All Cases)$O(n^2)$Requires $n(n-1)/2$ comparisons regardless of initial array order.
Space Complexity$O(1)$In-place algorithm. Requires no auxiliary storage.
StabilityNoSwaps can change the relative order of equal keys.
AdaptivityNoTakes the same time even if the array is already sorted.

7.1 Selection Sort: Dry Run

Tracing arr = [64, 25, 12, 22, 11]

PassUnsorted PortionMin FoundSwap ActionArray State after Swap
Init[64, 25, 12, 22, 11]——[64, 25, 12, 22, 11]
Pass 1[64, 25, 12, 22, 11]11 (idx 4)Swap 64 ↔ 11[11, | 25, 12, 22, 64]
Pass 2[25, 12, 22, 64]12 (idx 2)Swap 25 ↔ 12[11, 12, | 25, 22, 64]
Pass 3[25, 22, 64]22 (idx 3)Swap 25 ↔ 22[11, 12, 22, | 25, 64]
Pass 4[25, 64]25 (idx 3)No swap[11, 12, 22, 25, | 64]
Done———[11, 12, 22, 25, 64] ✓

7.1 Selection Sort: Interactive Visualizer

Summary

Observe selection sort scanning the array for the minimum value (blue) and placing it at the sorted boundary (green).

Applications

  • Useful when write operations are extremely expensive (performs at most $O(n)$ swaps).
  • Embedded hardware with flash storage or EEPROM.

📖 Ref: TutorialsPoint — Selection Sort

Default
Current i
Minimum
Comparing
Swap
Sorted

Press Play to begin...

Speed:

7.1 Selection Sort Code & Pseudocode

1. For i = 0 to n-2:
2.   min_idx = i
3.   For j = i+1 to n-1:
4.     If arr[j] < arr[min_idx]: min_idx = j
5.   Swap arr[i] ↔ arr[min_idx]
procedure selectionSort(A, n)
    for i = 0 to n-1
        min_idx = i
        for j = i+1 to n-1
            if A[j] < A[min_idx]
                min_idx = j
        swap(A[i], A[min_idx])
end procedure
void selectionSort(int arr[], int n) {
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++) {
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        // Swap only if needed
        if (min_idx != i) {
            int temp = arr[i];
            arr[i] = arr[min_idx];
            arr[min_idx] = temp;
        }
    }
}
#include <vector>
#include <algorithm>
using namespace std;

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; ++i) {
        int min_idx = i;
        for (int j = i + 1; j < n; ++j)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        if (min_idx != i)
            swap(arr[i], arr[min_idx]);
    }
}

7.2 Insertion Sort: Concept & Complexity

Concept

Insertion sort builds the sorted array one element at a time by picking an element (the key) from the unsorted part and inserting it into its correct relative position in the sorted part. Elements larger than the key are shifted right to create space.

Complexity Analysis

Case / MetricComplexityDescription
Best Case$O(n)$Occurs when array is already sorted. Only 1 comparison per element.
Average / Worst Case$O(n^2)$Requires nested shifting for reverse or unsorted inputs.
Space Complexity$O(1)$In-place. Requires no auxiliary storage.
StabilityYesMaintains original relative order of equal keys.
AdaptivityYesHighly adaptive. Fast on nearly-sorted data.

7.2 Insertion Sort: Dry Run

Tracing arr = [12, 11, 13, 5, 6]

Step / iKeyShifting ActionsArray State after Insertion
Init——[12, | 11, 13, 5, 6]
Step 1 (i=1)11Compare 11 < 12. Shift 12 right.[11, 12, | 13, 5, 6]
Step 2 (i=2)13Compare 13 > 12. No shifts.[11, 12, 13, | 5, 6]
Step 3 (i=3)5Shift 13, 12, 11 right. Insert 5 at index 0.[5, 11, 12, 13, | 6]
Step 4 (i=4)6Shift 13, 12, 11 right. Insert 6 at index 1.[5, 6, 11, 12, 13] ✓

7.2 Insertion Sort: Interactive Visualizer

Summary

Observe elements (blue) being inserted into their correct spot in the sorted sub-array (green), shifting elements right (yellow).

Applications

  • Small datasets or online data streams.
  • Used inside hybrid algorithms like Timsort (Python) or block sorts.
Default
Key
Shifting
Inserted
Sorted

Press Play to begin...

Speed:

7.2 Insertion Sort Code & Pseudocode

1. For i = 1 to n-1:
2.   key = arr[i]; j = i - 1
3.   While j >= 0 AND arr[j] > key:
4.     arr[j+1] = arr[j]; j--
5.   arr[j+1] = key
procedure insertionSort(A, n)
    for i = 1 to n-1
        key = A[i]
        j = i - 1
        while j >= 0 and A[j] > key
            A[j+1] = A[j]
            j = j - 1
        A[j+1] = key
end procedure
void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}
#include <vector>
using namespace std;

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

7.3 Quick Sort: Concept & Complexity

Concept

QuickSort is a Divide and Conquer algorithm. It selects a pivot element and partitions the array so all elements smaller than the pivot come before it, and all greater elements come after. Then recursively sorts the sub-arrays.

Complexity Analysis

Case / MetricComplexityDescription
Best Case$O(n \log n)$Occurs when partition divides array into equal halves.
Average Case$O(n \log n)$Uniform distribution of keys. Very fast in practice.
Worst Case$O(n^2)$Occurs when pivot is consistently the smallest or largest element.
Space Complexity$O(\log n)$Requires stack space for recursive calls (worst case is $O(n)$).
StabilityNoSwaps over pivot boundaries can rearrange identical keys.

7.3 Quick Sort: Dry Run

Tracing Partition on arr = [10, 80, 30, 90, 40, 50, 70]

Step / ScopePivotPartition SwapsArray State after Partition
L1 [0..6]70Swap (80,40), Swap (90,70)[10, 30, 40, 50, 70*, 90, 80]
L2 [0..3]5010, 30, 40 already < 50 (No swaps)[10, 30, 40, 50*, 70, 90, 80]
L3 [5..6]80Swap (90,80)[10, 30, 40, 50, 70, 80*, 90]
Done——[10, 30, 40, 50, 70, 80, 90] ✓

7.3 Quick Sort: Interactive Visualizer

Summary

Watch QuickSort select pivots (purple) and group smaller elements left (yellow) and larger right (default).

Applications

  • High-performance systems where average sorting speeds are prioritized.
  • Used in standard libraries (C++ `std::sort`, Java DualPivotQuickSort).
Default
Pivot
Comparing
Swap
Sorted

Press Play to begin...

Speed:

7.3 Quick Sort Code & Pseudocode

Partition(arr, low, high):
  pivot = arr[high]; i = low - 1
  For j = low to high-1:
    If arr[j] < pivot: i++; swap(arr[i], arr[j])
  swap(arr[i+1], arr[high]); return i+1

QuickSort(arr, low, high):
  If low < high:
    pi = Partition(arr, low, high)
    QuickSort(arr, low, pi-1)
    QuickSort(arr, pi+1, high)
procedure quickSort(A, low, high)
    if low < high
        pi = partition(A, low, high)
        quickSort(A, low, pi - 1)
        quickSort(A, pi + 1, high)

procedure partition(A, low, high)
    pivot = A[high]; i = low - 1
    for j = low to high - 1
        if A[j] <= pivot: i++; swap(A[i], A[j])
    swap(A[i+1], A[high])
    return i + 1
int partition(int arr[], int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; j++)
        if (arr[j] <= pivot) {
            int t = arr[++i]; arr[i] = arr[j]; arr[j] = t;
        }
    int t = arr[i+1]; arr[i+1] = arr[high]; arr[high] = t;
    return i + 1;
}
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}
#include <vector>
#include <algorithm>
using namespace std;

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high], i = low - 1;
    for (int j = low; j < high; ++j)
        if (arr[j] <= pivot) swap(arr[++i], arr[j]);
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

7.4 Merge Sort: Concept & Complexity

Concept

Merge Sort is a stable Divide and Conquer algorithm. It recursively splits the array into two halves, sorts each half, and then merges them back into a single sorted array using an auxiliary temporary buffer.

Complexity Analysis

Case / MetricComplexityDescription
Time Complexity (All Cases)$O(n \log n)$Guaranteed performance. Split trees and linear merging cost.
Space Complexity$O(n)$Requires additional temporary memory space to copy and merge halves.
StabilityYesPreserves relative ordering. Copies elements from left subarray first on tie.
AdaptivityNoPerforms partition and merge cycles regardless of initial order.

7.4 Merge Sort: Dry Run

Tracing arr = [38, 27, 43, 3]

PhaseSub-array (Left)Sub-array (Right)Merged Array State
Split 1[38, 27][43, 3]Separation complete. Recursion begins.
Sort Left[38] ↔ [27]—[27, 38, | 43, 3]
Sort Right—[43] ↔ [3][27, 38, | 3, 43]
Merge Final[27, 38][3, 43][3, 27, 38, 43] ✓

7.4 Merge Sort: Interactive Visualizer

Summary

Observe elements sorted recursively in partitioned ranges (yellow) and merged back as a sorted sequence (blue/green).

Applications

  • External sorting (sorting data files larger than RAM).
  • Recommended for sorting linked list elements.
Default
Bounds
Comparing
Placed
Merged Range

Press Play to begin...

Speed:

7.4 Merge Sort Code & Pseudocode

mergeSort(arr, l, r):
  If l < r:
    m = (l + r) / 2
    mergeSort(arr, l, m)
    mergeSort(arr, m+1, r)
    merge(arr, l, m, r)

merge(arr, l, m, r):
  Copy arr[l..m] → L[], arr[m+1..r] → R[]
  Compare L[i] and R[j], place smaller into arr[k]
procedure mergeSort(A, l, r)
    if l < r
        m = l + (r - l) / 2
        mergeSort(A, l, m)
        mergeSort(A, m+1, r)
        merge(A, l, m, r)

procedure merge(A, l, m, r)
    Create L[0..n1], R[0..n2]
    i = 0; j = 0; k = l
    while i < n1 and j < n2
        if L[i] <= R[j]: A[k++] = L[i++]
        else: A[k++] = R[j++]
void merge(int a[], int l, int m, int r) {
    int n1=m-l+1, n2=r-m, i, j, k;
    int L[n1], R[n2];
    for(i=0;i<n1;i++) L[i]=a[l+i];
    for(j=0;j<n2;j++) R[j]=a[m+1+j];
    i=0; j=0; k=l;
    while(i<n1 && j<n2)
        a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
    while(i<n1) a[k++]=L[i++];
    while(j<n2) a[k++]=R[j++];
}
void mergeSort(int a[], int l, int r) {
    if(l<r){ int m=l+(r-l)/2;
        mergeSort(a,l,m); mergeSort(a,m+1,r);
        merge(a,l,m,r); }
}
#include <vector>
using namespace std;

void merge(vector<int>& a, int l, int m, int r) {
    vector<int> L(a.begin()+l, a.begin()+m+1);
    vector<int> R(a.begin()+m+1, a.begin()+r+1);
    int i=0,j=0,k=l;
    while(i<L.size()&&j<R.size())
        a[k++]=(L[i]<=R[j])?L[i++]:R[j++];
    while(i<L.size()) a[k++]=L[i++];
    while(j<R.size()) a[k++]=R[j++];
}
void mergeSort(vector<int>& a, int l, int r){
    if(l<r){ int m=l+(r-l)/2;
        mergeSort(a,l,m); mergeSort(a,m+1,r);
        merge(a,l,m,r); }
}

7.5 Heap Sort: Concept & Complexity

Concept

Heap Sort uses a Binary Max-Heap structure. The input is transformed into a heap (parent element larger than children). The largest element (root) is repeatedly swapped with the last element of the heap, and heap size decreases as heapify restores Max-Heap rules.

Complexity Analysis

Case / MetricComplexityDescription
Time Complexity (All Cases)$O(n \log n)$Guaranteed time bound due to heap traversal of height $\log n$.
Space Complexity$O(1)$In-place. Avoids recursive stack allocation inside helper loops.
StabilityNoNon-adjacent leaf/root tree exchanges can change equal keys.
AdaptivityNoAlways requires heap structure generation and extraction cycles.

7.5 Heap Sort: Dry Run

Tracing arr = [4, 10, 3, 5, 1]

PhaseActionHeap State & Auxiliary InfoArray Representation
HeapifyMax-Heapify from idx 1 down to 0Root is now max value[10, 5, 3, 4, 1]
Extract 1Swap root 10 ↔ 1; Heapify remainingMax 10 placed at last position[5, 4, 3, 1 | 10]
Extract 2Swap root 5 ↔ 1; Heapify remainingMax 5 placed at index 3[4, 1, 3 | 5, 10]
Extract 3Swap root 4 ↔ 3; Heapify remainingMax 4 placed at index 2[3, 1 | 4, 5, 10]
Extract 4Swap root 3 ↔ 1Sorted array complete[1, 3, 4, 5, 10] ✓

7.5 Heap Sort: Interactive Visualizer

Summary

HeapSort constructs a max heap. The root (purple) represents the maximum and gets swapped to the sorted end (green).

Applications

  • Recommended when guaranteed time performance and low memory use are key constraints.
  • Used in real-time embedded safety critical control systems.
Default
Parent
Child
Swap
Sorted

Press Play to begin...

Speed:

7.5 Heap Sort Code & Pseudocode

heapify(arr, n, i):
  largest = i; l=2i+1; r=2i+2
  If l<n and arr[l]>arr[largest]: largest=l
  If r<n and arr[r]>arr[largest]: largest=r
  If largest != i: swap; heapify(arr, n, largest)

heapSort(arr, n):
  For i = n/2-1 down to 0: heapify(arr, n, i)
  For i = n-1 down to 1:
    swap(arr[0], arr[i]); heapify(arr, i, 0)
procedure heapify(A, n, i)
    largest = i; l = 2*i+1; r = 2*i+2
    if l < n and A[l] > A[largest]: largest = l
    if r < n and A[r] > A[largest]: largest = r
    if largest != i
        swap(A[i], A[largest])
        heapify(A, n, largest)

procedure heapSort(A, n)
    for i = n/2-1 downto 0: heapify(A, n, i)
    for i = n-1 downto 1
        swap(A[0], A[i]); heapify(A, i, 0)
void heapify(int a[], int n, int i) {
    int lg=i, l=2*i+1, r=2*i+2;
    if(l<n && a[l]>a[lg]) lg=l;
    if(r<n && a[r]>a[lg]) lg=r;
    if(lg!=i){ int t=a[i];a[i]=a[lg];a[lg]=t;
        heapify(a,n,lg); }
}
void heapSort(int a[], int n) {
    for(int i=n/2-1;i>=0;i--) heapify(a,n,i);
    for(int i=n-1;i>0;i--){
        int t=a[0];a[0]=a[i];a[i]=t;
        heapify(a,i,0);
    }
}
#include <vector>
#include <algorithm>
using namespace std;

void heapify(vector<int>& a, int n, int i) {
    int lg=i, l=2*i+1, r=2*i+2;
    if(l<n && a[l]>a[lg]) lg=l;
    if(r<n && a[r]>a[lg]) lg=r;
    if(lg!=i){ swap(a[i],a[lg]); heapify(a,n,lg); }
}
void heapSort(vector<int>& a){
    int n=a.size();
    for(int i=n/2-1;i>=0;i--) heapify(a,n,i);
    for(int i=n-1;i>0;i--){
        swap(a[0],a[i]); heapify(a,i,0);
    }
}

7.6 Shell Sort: Concept & Complexity

Concept

Shell Sort is an enhanced version of Insertion Sort. It compares elements separated by a gap. The gap sequence is gradually reduced to 1 (which acts as a final standard Insertion Sort). This minimizes shifts by allowing exchanges of far-apart elements.

Complexity Analysis

Case / MetricComplexityDescription
Best Case$O(n \log n)$Occurs on nearly-sorted lists with optimal gap sequences.
Average CaseDepends on gap sequenceOften around $O(n^{1.25})$ or $O(n^{1.5})$ depending on gaps.
Worst Case$O(n^2)$Shell's original sequence $n/2^k$ worst case is $O(n^2)$.
Space Complexity$O(1)$In-place. Requires no stack or extra variables.
StabilityNoInterspersed group swaps can alter stable key sequences.

7.6 Shell Sort: Dry Run

Tracing arr = [9, 5, 7, 3, 6, 2]

Pass / GapGroupings SortedComparisons & ActionArray State after Pass
Init——[9, 5, 7, 3, 6, 2]
Gap = 3(0,3), (1,4), (2,5)Compare (9,3) → Swap, (5,6) → No, (7,2) → Swap[3, 5, 2, 9, 6, 7]
Gap = 1Full ArrayRun standard insertion sort on nearly-sorted data[2, 3, 5, 6, 7, 9] ✓

7.6 Shell Sort: Interactive Visualizer

Summary

Observe ShellSort comparing far-apart elements with gap segments (yellow), shrinking gaps to sort efficiently.

Applications

  • Embedded platforms where call stack space must be strictly avoided.
  • Faster than selection and insertion sort for medium-sized databases.
Default
Key
Comparing
Shifting
Inserted

Press Play to begin...

Speed:

7.6 Shell Sort Code & Pseudocode

shellSort(arr, n):
  For gap = n/2 down to 1 (gap /= 2):
    For i = gap to n-1:
      temp = arr[i]
      j = i
      While j >= gap and arr[j-gap] > temp:
        arr[j] = arr[j-gap]; j -= gap
      arr[j] = temp
procedure shellSort(A, n)
    gap = n / 2
    while gap > 0
        for i = gap to n-1
            temp = A[i]; j = i
            while j >= gap and A[j-gap] > temp
                A[j] = A[j-gap]; j -= gap
            A[j] = temp
        gap = gap / 2
void shellSort(int arr[], int n) {
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int temp = arr[i], j = i;
            for (; j >= gap && arr[j-gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}
#include <vector>
using namespace std;

void shellSort(vector<int>& arr) {
    int n = arr.size();
    for (int gap = n/2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; ++i) {
            int temp = arr[i], j = i;
            for (; j >= gap && arr[j-gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
            arr[j] = temp;
        }
    }
}

Sorting Algorithm Comparison

AlgorithmBest TimeAvg TimeWorst TimeSpaceStableAdaptive
Selection Sort$O(n^2)$$O(n^2)$$O(n^2)$$O(1)$NoNo
Insertion Sort$O(n)$$O(n^2)$$O(n^2)$$O(1)$YesYes
Quick Sort$O(n\log n)$$O(n\log n)$$O(n^2)$$O(\log n)$NoNo
Merge Sort$O(n\log n)$$O(n\log n)$$O(n\log n)$$O(n)$YesNo
Heap Sort$O(n\log n)$$O(n\log n)$$O(n\log n)$$O(1)$NoNo
Shell Sort$O(n\log n)$Depends$O(n^2)$$O(1)$NoYes