Class BinaryInsertion

java.lang.Object
topics.sorting.insertion.BinaryInsertion
All Implemented Interfaces:
SortingAlgorithm
public class BinaryInsertion extends Object implements SortingAlgorithm

Binary Insertion Sort

An educational optimization of the standard Direct Insertion Sort. Instead of sequentially scanning backwards to find the correct insertion point for the new element (the key), this variant employs a Binary Search upon the already sorted sub-array.

Algorithm Steps

  1. Assume the first element (index 0) is sorted.
  2. Pick the next element as the key.
  3. Use Binary Search O(log N) on the sorted left portion to find the exact insertion index.
  4. Shift all elements from the insertion index up to the current boundary one position to the right.
  5. Place the key into the newly vacated position.

Complexity Analysis

  • Time Complexity (Comparisons): O(N log N) - Binary search drastically reduces the number of comparisons.
  • Time Complexity (Swaps/Shifts): O(N²) - Moving elements in an array still requires linear shifting, dominating the overall time complexity in average/worst cases.
  • Space Complexity: O(1) - Sorts entirely in-place.
  • Stability: Yes - Because the binary search condition (key invalid input: '<' elements[center]) forces the algorithm to place equal elements to the right of existing ones.
Author:
vicegd
See Also:
  • invalid reference 
    topics.sorting.SortingAlgorithm

  • Constructor Summary

    Constructors
    Constructor
    Description
    BinaryInsertion()
     

  • Method Summary

    Modifier and Type
    Method
    Description
    void
    sort(int[] elements)
    Sorts the elements in-place silently.
    void
    sort(int[] elements, boolean trace)
    Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.

    Methods inherited from class Object

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

  • Constructor Details

    • BinaryInsertion

      public BinaryInsertion()

  • Method Details

    • sort

      public void sort(int[] elements)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place silently.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.

    • sort

      public void sort(int[] elements, boolean trace)
      Description copied from interface: SortingAlgorithm
      Sorts the elements in-place, optionally emitting step-by-step traces to visualize the algorithmic progression.
      Specified by:
      sort in interface SortingAlgorithm
      Parameters:
      elements - The array of integers to be sorted.
      trace - If true, logs the internal state during execution.