private void insert(int[] a, int left, int right, int value) {
        int i = right-1;
        while (i >= left && a[i] > value) {
            a[i+1] = a[i];
            i--;
        }
        a[i+1] = value;
    }
    
    private void insertionSort(int[] a, int left, int right) {
        int i = left;
        while (i < right) {
            insert(a, left, right, a[i]);
            i++;
        }
    }