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 Details

    • BinaryInsertion

      public BinaryInsertion()

  • 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.