二分法实现插入排序，时间复杂度O（nlgn），算法导论练习2.3，linux纯C实现
#include <stdio.h>int binarySearch(int* a, int fI, int lI, int N){int mI = (fI+lI) >> 1;if (N > *(a+mI)){fI = mI + 1;if(fI > lI)return mI+1;binarySearch(a, fI, lI, N);}else if (N < *(a+mI)){lI = mI - 1;if(fI > lI)return mI;binarySearch(a, fI, lI, N);}elsereturn mI+1;}void insertSort(int* a, int index, int N){int key = *(a+index);if(index+1 <= N){int i = binarySearch(a, 0, index-1, key);int j = index-1;for (;j>=i;j--){*(a+j+1) = *(a+j);}*(a+i) = key;insertSort(a, index+1, N);}return;}int main(){int a[10] = {212,343,534,2,3,67,34,78,90,32};int L = sizeof(a)/sizeof(int);int i = 0;insertSort(a, 1, L);for (;i<L;i++)printf("%d ",*(a+i));printf("\n");return 0;}