about insertion sort improvement in Robert Sedgewick

Viewed 961

I am reading about algorithms by Robert Sedgewick book.

public static void sort(Comparable[] a)
{   // Sort a[] into increasing order.
    int N = a.length;
    for (int i = 1; i < N; i++)
    { // Insert a[i] among a[i-1], a[i-2], a[i-3]... ..
        for (int j = i; j > 0 && less(a[j], a[j-1]); j--)
            exch(a, j, j-1);
    }
}

Above is insertion sort implementation in java. Here author mentiones as improvment as below.

It is not difficult to speed up insertion sort substantially, by shortening its inner loop to move the larger entries to the right one position rather than doing full exchanges (thus cutting the number of array accesses in half)

I am having difficutly in understanding above improvement. What does author mean by

  1. Move large entries to the right one postion rather than full exchanges and how this will reduce array access to half.

Request to example with simple example for better understanding.

1 Answers
Related