Insertion Sort

Java Implementation

/*
==========================================================
Generic Implementation of Insertion sort
Input: Used Comparable interface as input

Input: [ 3, 0, 5, 2, 1, 0, 0, 0, 4 ]
Output: [ 0, 0, 0, 0, 1, 2, 3, 4, 5 ]

Input: [ "three", "0", "five", "2", "one", "seven", "4" ]
Output: [ "0", "2", "4", "five", "one", "seven", "three" ]

==========================================================
*/

public static class Insertion {
    public int partition(Comparable[] a, int low, int high) {
      int i = low, j = high + 1;
      while (true) {
        while (compare(a[++i], a[low])) if (i == high) break;
        while (compare(a[low], a[--j])) if (j == low) break;
        if (i >= j) break;
        swap(a, i, j);
      }
      swap(a, low, j);
      return j;
    }

    void sort(Comparable[] a, int low, int high) {
      if (low < high) {
        int pi = partition(a, low, high);
        sort(a, low, pi - 1);
        sort(a, pi + 1, high);
      }
    }

    private void swap(Comparable[] a, int i, int j) {
      Comparable swap = a[i];
      a[i] = a[j];
      a[j] = swap;
    }

    private boolean compare(Comparable comparable, Comparable comparable1) {
      return comparable.compareTo(comparable1) < 0;
    }
  }

Properties

• Stable

• $O(1)$ extra space

• $O(n^{2})$ comparisons and swaps

• Adaptive: $O(n)$ time when nearly sorted

• Very low overhead