adaptive insertion sort

👍 g++ -std=c++11 program63.cpp
👍 ./a.out 7 1
138 139 264 353 700 789 835 
👍 ./a.out 7 1
264 364 374 493 646 884 917 
👍 ./a.out 7 0
2 7 1 8 2 8 1
1 1 2 2 7 8 8 

👍 cat program63.cpp 
#include <iostream>
using namespace std;

template <typename T>
void exch(T &a, T &b)
  { T t = a; a = b; b = t; }
template <typename T>
void compexch(T &a, T &b)
  { if (b < a) exch(a, b); }

template <typename T>
void insertion(T a[], int l, int r)
{
  int i;
  for (i = r; i > l; i--)
    compexch(a[i-1], a[i]);
  for( int i = l+2; i <= r; i++) {
    int j = i; T v = a[i];
    while (v < a[j-1])
      { a[j] = a[j-1]; j--; }
    a[j] = v;
  }
}

int main(int argc, char *argv[])
{
  int i, N = atoi(argv[1]), 
        sw = atoi(argv[2]);
  int *a = new int[N];
  srand(time(0));
  if (sw)
    for (i = 0; i < N; i++)
      a[i] = 1000*(1.0*rand()/RAND_MAX);
  else 
    { N = 0; while (cin >> a[N]) N++; } 
  insertion(a, 0, N-1);
  for (i = 0; i < N; i++) cout << a[i] << " ";
  cout << endl;
}

    

ch 6.3 Insertion Sort p276 of