Straight insertion sort

This documentation was generated with the assistance of AI. Please report any inaccuracies.

StraightInsertionSorter sorts an array by straight insertion, the technique used by card players to sort a hand of cards: pick out the second card and put it in order with respect to the first; then pick out the third card and insert it among the first two; and so on until the last card has been inserted.

Because it compares and shifts elements one at a time, straight insertion is an O(N²) algorithm. It is nevertheless useful for small arrays (roughly N < 20), where its low overhead per element makes it faster in practice than asymptotically better algorithms such as Quicksort or Heapsort. For larger arrays, Shell sort is a simple extension of the same idea that scales much better.

StraightInsertionSorter is stable: elements that compare as equal keep their relative order.

Example

The diagram below traces StraightInsertionSorter over the array {5, 3, 8, 1, 9} used in the usage example below. Each row is the array state after pass j; the element just picked out and inserted is highlighted, and the growing sorted prefix is outlined.

Straight insertion sort passes over the array 5 3 8 1 9

Usage

import com.irurueta.sorting.StraightInsertionSorter;

StraightInsertionSorter<Double> sorter = new StraightInsertionSorter<>();

double[] values = {5.0, 3.0, 8.0, 1.0, 9.0};
sorter.sort(values);

It can also be selected dynamically through the Sorter factory:

import com.irurueta.sorting.Sorter;
import com.irurueta.sorting.SortingMethod;

Sorter<Double> sorter = Sorter.create(SortingMethod.STRAIGHT_INSERTION_SORTING_METHOD);

Like every Sorter, it also supports sortWithIndices, select and median, as described in Usage.

Reference

This class is based on the algorithm described in Numerical Recipes, 3rd Edition, section 8.1, "Straight Insertion and Shell’s Method".