#include <stdio.h>
#include <string.h>
#define max 10
#define SIZE sizeof(int)/sizeof(char)
void sort(int input[], int n);
int main()
{int a[max],i;
printf("================================================\n");
for(i=0;i<max;i++)
{scanf("%d",&a[i]);}
for(i=0;i<max;i++)
printf("%4d",a[i]);
printf("\n\n\n");
sort(a,max);
for(i=0;i<max;i++)
printf("%4d",a[i]);
printf("\n");
getch();
return 0;
}
void sort(int input[], int n)
{
int current, pos;
int low, high, mid;
int x;
for (current = 1; current < n; current++) {
x = input[current];
pos = -1; /* pos=-1 means DON'T move */
if (x < input[0]) /* insert before head ? */
pos = 0; /* YES, set pos to 0. */
else if (x <= input[current-1]) { /* bin search */
low = 0; /* low index. */
high = current - 1; /* high index */
while (high - low > 1) { /* stop? */
mid = (low + high) / 2; /* the mid pt */
if (x >= input[mid])
low = mid; /* try right */
else
high = mid; /* try left */
}
pos = low + 1;
}
if (pos >= 0) { /* move a block */
memmove((void *) &input[pos+1], (void *) &input[pos],
SIZE*(current-pos));
input[pos] = x;
}
}
}