Class DirectInsertion

java.lang.Object

topics.sorting.insertion.DirectInsertion

All Implemented Interfaces:

SortingAlgorithm

public class DirectInsertion
extends Object
implements SortingAlgorithm

Direct Insertion Sort

An educational sorting implementation that builds the final sorted array one item at a time. It operates similarly to how one might sort a hand of playing cards: picking an element and inserting it into its mathematically correct position among the already sorted elements to its left.

Algorithm Steps

1. Assume the first element (index 0) is already sorted.
2. Pick the next element, referred to as the key.
3. Compare the key with elements in the sorted sub-array to its left.
4. Shift all elements strictly greater than the key one position to the right.
5. Insert the key into the newly vacated correct position.
6. Repeat until the boundary reaches the end of the array.

Complexity Analysis

• Time Complexity (Worst/Average): O(N²) - Occurs when the array is in reverse order.
• Time Complexity (Best): O(N) - Occurs when the array is already sorted (the inner while loop never executes).
• Space Complexity: O(1) - Sorts entirely in-place without recursion overhead.
• Stability: Yes - Maintains the relative order of equal elements because it only shifts strictly greater elements.

Author:

vicegd

See Also:

• invalid reference

  topics.sorting.SortingAlgorithm

Constructor Summary

Constructors

Constructor	Description
DirectInsertion()

Method Summary

Modifier and Type	Method	Description
void	sort(int[] elements)	Sorts the elements in-place.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

DirectInsertion

public DirectInsertion()

Method Details

sort

public void sort(int[] elements)

Description copied from interface: SortingAlgorithm

Sorts the elements in-place.

Specified by:

sort in interface SortingAlgorithm

Parameters:

elements - The array of integers to be sorted.