void insertion_sort ( int *data, int n )
{
int i, j, remember;
  for ( i = 1; i < n; i++ )
  {
    remember = data[(j=i)];
    while ( --j >= 0 && remember < data[j] ) data[j+1] = data[j];
    data[j+1] = remember;
  }
}

/* 아래는 정렬되는 자료가 단순 데이터일 경우에 memcpy()로 자료를 밀어내는 예제 */
/* memcpy 는 자료를 당겨야하므로 비교를 역순으로 수행한다. */
/* memcpy 를 이용하면 위의 코드보다 25~30% 가량 빠르게 처리된다. */
void insertion_sort ( int *data, int n )
{
int i = n-2, j, remember;
  while ( i-- > 0 )  
  {
    remember = data[(j=i)];
    while ( ++j < n && remember > data[j] );
 
    if ( --j == i ) continue;
    memcpy ( data+i, data+i+1, sizeof(*data) * (j-i) );
    data[j] = remember;
  }
}

void insert(const Element e,Element *list,int i)
{
   while(e.getKey()<list[i].getKey())
   {
      list[i+1]=list[i]
      i--;
   }
   list[i+1]=e;
}

/*
* insertion Sort의 오름차순 정렬은 배열을 순차적으로(1~n) 까지 검색함.
* arr[] 는 int[]라고 가정함.
*/
 
void insertionSort(int[] arr)
{
 
   for(int index = 1 ; index < arr.length ; i++){
 
      int temp = arr[index];
      int aux = index - 1;
 
      while( (aux >= 0) && ( arr[aux] > temp) ) {
 
         arr[aux+1] = arr[aux];
         aux--;
      }
      index[aux + 1] = temp;
 
}

let rec isort = function
        | [] -> []
        | h::t -> insert h (isort t)
and insert a = function
        | [] -> [a]
        | h::t when a<h -> [a] @ (h::t)
        | h::t -> [h] @ (insert a t);;