public class InsertionSort{
    public static void InsertionSort(int[] a) {
        insertion_sort(a, a.length);
    }
    
    private static void insertion_sort(int[] a, int size){
        for (int i=1; i<size; i++){
            int k = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > k){
                a[j+1] = a[j];
                j--;
            }
            a[j+1] = k;
        }
    }
}

최선 시간 복잡도: O(N) 최악 시간 복잡도: O(N<sup>2)

L < R 이 될 때 까지 작은 수를 제일 왼쪽으로 밀어내는 알고리즘이다.