Shell sort operates as a generalized version of insertion sort that overcomes the limitation of moving elements only one position at a time. By initially comparing elements separated by a large gap, the algorithm rapidly shifts values closer to their final destinations. As the gap progressively shrinks, the array becomes increasingly ordered, allowing the final pass with a gap of one to execute efficiently.

The performance heavily depends on the chosen gap sequence. Donald Shell's original approach halves the array length repeatedly until the gap reaches one. More advanced sequences, such as Sedgewick's formula, yield better worst-case time complexity. The algorithm sorts in-place with O(1) auxiliary space, and its time complexity typically ranges between O(n log n) and O(n^2) depending on the increment strategy. Note that shell sort is inherently unstable.

public static void performShellSort(int[] dataset) {
    int n = dataset.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int currentValue = dataset[i];
            int j = i;
            while (j >= gap && dataset[j - gap] > currentValue) {
                dataset[j] = dataset[j - gap];
                j -= gap;
            }
            dataset[j] = currentValue;
        }
    }
}

Selecsion sort partitions the input into a sorted prefix and an unsorted suffix. During each iteration, the algorithm scans the unsorted portion to locate the minimum value and swaps it with the first element of that unsorted segment. This process expands the sorted region by one element per pass until the entire collection is ordered.

A defining characteristic of this approach is its minimal data movement. Since each swap places at least one element into its permanent position, the algorithm performs at most n-1 exchanges for an array of size n. This makes it advantageous in environments where write operations are costly. However, it consistently exhibits O(n^2) time complexity regardless of initial ordering and does not preserve the relative order of equal elements.

public static void executeSelectionSort(int[] collection) {
    int totalElements = collection.length;
    for (int boundary = 0; boundary < totalElements - 1; boundary++) {
        int minIndex = boundary;
        for (int scanner = boundary + 1; scanner < totalElements; scanner++) {
            if (collection[scanner] < collection[minIndex]) {
                minIndex = scanner;
            }
        }
        if (minIndex != boundary) {
            int placeholder = collection[boundary];
            collection[boundary] = collection[minIndex];
            collection[minIndex] = placeholder;
        }
    }
}