Insertion Sort - Java Code

A stable, in-place sort

• Worst case time complexity: O(n2)
• Best case time complexity: O(n)

Java Code

       public void insertionSort(int[] arr) {

              for (int i = 1; i < arr.length; ++i) {

                     int currentElement = arr[i];

                     int j = i;

                     while (j > 0 && arr[j - 1] > currentElement) {

                           arr[j] = arr[j - 1];

                           j--;

                     }

                     arr[j] = currentElement;

              }

       }