tag

#insertion-sort

8 pages tagged

Practice › LeetCode › LeetCode (archived) › LeetCode 01xx ›

LeetCode 147: Insertion Sort List

Problem Restatement We are given the head of a singly linked list. Sort the list using insertion sort and return the new head. Insertion sort builds a sorted output list one node at a time. At each step, it removes one node from the input, finds where it belongs in the sorted part, and inserts it there. LeetCode gives examples such as [4,2,1,3] -> [1,2,3,4] and [-1,5,3,4,0] -> [-1,0,3,4,5] ....
leetcode Medium linked-list sorting insertion-sort May 10, 2026
Programming › Algorithm Cookbook › Chapter 6. Sorting ›

6.3 Insertion Sort

6.3 Insertion Sort Insertion sort builds a sorted prefix one element at a time. At step i , the prefix A[0..i-1] is already sorted, and the algorithm inserts A[i] into its correct position inside that prefix. This is the same operation used when sorting cards by hand: keep the left side ordered, take the next card, and slide it left until it belongs. Problem You have an array A[0..n-1] ....
algorithms sorting insertion-sort May 4, 2026
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Binary Insertion Sort

Binary Insertion Sort Binary insertion sort improves insertion sort by using binary search to locate the correct insertion position in the sorted prefix. This reduces the number of comparisons, though element shifting still dominates the runtime. The algorithm keeps the same structure as insertion sort but replaces the linear scan with a logarithmic search. Problem Given a sequence $A$ of length $n$, reorder it such that $$ A[0] \le A[1]...
algorithms sorting insertion-sort binary-search
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Library Sort

Library Sort Library sort is an insertion-based sorting algorithm that leaves empty spaces between stored elements. These gaps make later insertions cheaper because elements often move only a short distance instead of shifting an entire suffix. The idea is similar to leaving empty spaces on a bookshelf so new books can be inserted without moving many existing books. Problem Given a sequence $A$ of length $n$, reorder it such that...
algorithms sorting library-sort insertion-sort
Wiki › Algorithms › 01. Searching and Sorting › 6. Elementary Sorting ›

Insertion Sort

Insertion Sort Insertion sort builds the sorted array one element at a time. At each step, it takes the next element and inserts it into the correct position within the already sorted prefix. It mirrors the process of sorting cards in hand. Compared to swap-based methods, it reduces writes by shifting elements. Problem Given a sequence $A$ of length $n$, reorder it such that $$ A[0] \le A[1] \le \cdots...
algorithms sorting insertion-sort arrays
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Insertion Sort with Sentinel

Insertion Sort with Sentinel Insertion sort with sentinel is a small optimization of insertion sort. It first places the minimum element at the beginning of the array. That element acts as a sentinel, so the inner loop can stop without checking whether it has reached the start of the array. You use it when implementing insertion sort as a low-level routine, especially inside hybrid sorts. Problem Given an array (...
algorithms sorting insertion-sort sentinel adaptive
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Online Insertion Sort

Online Insertion Sort Online insertion sort is insertion sort used in an online setting. It accepts elements one at a time and keeps all seen elements sorted after each insertion. You use it when the input is not available all at once, but the sorted prefix must remain queryable during processing. Problem Given a stream of values ( x_1, x_2, \dots, x_n ), maintain a sorted sequence ( S )...
algorithms sorting online insertion-sort
Wiki › Algorithms › 01. Searching and Sorting › 9. Partial, Online, and Adaptive Sorting ›

Nearly Sorted Insertion Sort

Nearly Sorted Insertion Sort Nearly sorted insertion sort is ordinary insertion sort applied to input that is already close to sorted order. Insertion sort adapts well to this case because each element moves only a short distance. You use it when the input has small disorder, such as data produced by appending a few new records, merging mostly ordered logs, or correcting a sequence after minor edits. Problem Given an...
algorithms sorting adaptive insertion-sort nearly-sorted