Insertion & Selection Sort

Insertion sort and selection sort are two simple comparison sorts that both run in O(n2) time on average. They differ in strategy: insertion sort grows a sorted region by inserting each new element into its correct spot, while selection sort repeatedly finds the smallest remaining element and places it next. Both are easy to understand, sort in place, and are practical only for small inputs.

Insertion sort: build the sorted part one element at a time

Insertion sort treats the front of the array as a growing sorted region. It takes the next unsorted element and slides it left, past every larger element, until it lands in the right place — exactly how many people sort a hand of playing cards.

#include <iostream>
using namespace std;

// Insertion sort, ascending. Average and worst case O(n^2);
// best case O(n) when the array is already sorted.
void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];   // the element to insert into the sorted part
        int j = i - 1;

        // Shift larger elements one slot right to open a gap for key.
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;   // drop key into its correct position
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " "; // 1 2 5 6 9
    return 0;
}

Insertion sort is adaptive: on nearly sorted data the inner while loop barely runs, so it approaches O(n). It is also stable and does few writes when data is close to sorted, which is why it is often used as the base case inside faster algorithms for small subarrays.

Selection sort: find the smallest, then place it

Selection sort scans the unsorted region to find the smallest element, swaps it into the first unsorted slot, and repeats. The sorted region grows from the front, one guaranteed-smallest element at a time.

#include <iostream>
using namespace std;

// Selection sort, ascending. Always O(n^2) comparisons,
// even if the array is already sorted, but at most n-1 swaps.
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // assume the current position holds the smallest

        // Scan the rest of the array for anything smaller.
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(arr[i], arr[minIndex]); // put the smallest into position i
    }
}

int main() {
    int arr[] = {5, 2, 9, 1, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    for (int i = 0; i < n; i++) cout << arr[i] << " "; // 1 2 5 6 9
    return 0;
}

Selection sort always scans the full remaining region, so it is O(n2) regardless of input order — it is not adaptive. Its one redeeming feature is that it performs at most n - 1 swaps, which matters when writing to memory is expensive.

How they compare

Insertion sort usually wins for nearly sorted data and as a small-array helper inside merge sort or quick sort. Selection sort is mainly of academic interest, useful only when minimising the number of writes is the priority.

When to use either

Both are good choices only for small arrays or when simplicity matters more than speed. For anything large, switch to an O(n log n) algorithm. Insertion sort's adaptivity and stability make it the more practically useful of the two.

Common mistakes

• Expecting selection sort to speed up on sorted input. It always does the full O(n2) scan. Only insertion sort short-circuits on near-sorted data.
• Wrong shift direction in insertion sort. You shift larger elements right to open a gap, then drop the key in. Overwriting arr[i] before saving it into key loses the value.
• Off-by-one in the inner loop. Selection sort's inner loop starts at i + 1; insertion sort's outer loop starts at 1. Starting at the wrong index silently skips or misplaces elements.
• Assuming selection sort is stable. The long-distance swap can reorder equal elements. Plain insertion sort preserves their order.
• Using either on large data. Both are O(n2). For big inputs they are far slower than merge or quick sort.

FAQ

Which is faster in practice? Insertion sort, on most realistic data, especially when it is partly sorted. Selection sort's only edge is fewer swaps.

Why learn these at all? They build intuition for how sorting works and appear as the small-array base case inside production sorts. Understanding them makes the faster algorithms easier to grasp.

Keep learning

Start with Bubble Sort for the simplest case, then move up to the divide-and-conquer Merge Sort. Ground the costs with Big-O Notation, and browse the full DSA hub.

Want to master sorting with instructor feedback in Jalgaon? Join the waitlist for our Data Structures & Algorithms course.