百度笔试算法题一道。

一个数组a[0-n-1],a[0-mid]和a[mid+1-n-1]是各自升序的，现在要把a[0-n-1]排成有序的。要求空间复杂度o(1)，时间复杂度尽量低。

我想到的方法就是将后面序列的每个元素对前面序列进行插入排序。搜索插入位置的时候考虑从上一个插入元素位置之后开始搜索。
说明一下这个方法时间复杂度最坏应该是o(n^2)，网上有o(n)解法。

#include <stdlib.h>
int insert(int* a, int begin, int end, int x){
	int pos = end;	//插入位置 
	int last = a[end];
	int exchange = 0;
	int i;
	//寻找插入位置 
	for(i = begin; i <= end; i++){
		if(a[i] > x){
			pos = i;
			exchange = 1;
			break;
		}
	}
	if(exchange){
		//移动元素 
		for(i = end; i > pos; i--){
			a[i] = a[i-1];
		}	
		a[end+1] = last;
		a[pos] = x;
	}else{
		pos = end+1;
	}
	return pos;
}

void print_r(int* a, int n){
	int i = 0;
	while(i<n){
		printf("%d\t",a[i++]);
	}
	printf("\n");
}

void merge(int* a, int n, int mid){
	int search_begin = 0;
	int i;
	for(i = mid; i < n; i++){
		search_begin = insert(a,search_begin, i, a[i+1]);	
	}
}

int main(){
	int a[10] = {
	1,2,3,7,9,0,4,10,18,20
	};
	int mid = 4;
	merge(a,10,mid);
	print_r(a,10);
	return 0;
}