Running Time

On my (fairly old) computer it takes about 204 seconds to sort an array of 500 thousand ints. Of course, the length of time it takes depends on the particular integers sorted since the inner loop continues only as long as it takes to find the right spot for the current integer. Run the program 10 times with different random integers to get a better measure of the running time.

Look at the central part of the algorithm:

    //  For each unsorted integer
    for (int j = 1; j < list.length; j++)
    {

       //  Keep swapping with its left neighbor 
       //  until it is larger or equal to left neighbor
       int k = j;
       while (k > 0 && list[k-1] > list[k] )
       {
          int temp  = list[k-1];
          list[k-1] = list[k];
          list[k]   = temp;
          k--;
       }
    }

Say that there are N ints in the array. (In other words, list.length == N). Then the code can be simplified:

for (int j = 1; j < N; j++)
{
   while (k > 0 && list[k-1] > list[k] )
   {
      // swap 
      k--;
   }
}

Notice that j is the index of the integer about to be inserted into its proper place, and is also the current size of the sorted sub-list. So the algorithm can be further simplified to:

for (int j = 1; j < N; j++)
{
  loop: insert list[j] into its proper place in sub-list of size j
}