今天接到电话面试的时候提到了一个归并排序，之前用的比较少，于是完了之后参照 http://blog.csdn.net/morewindo… 写了一个归并排序

#include <stdio.h>
#include <stdlib.h>

void merge(int n[], int first, int mid, int last, int temp[])
{
	int i=first, j=mid+1, k=0;
	while (i<=mid && j<=last)
	{
		if (n[i] < n[j])
		{
			temp[k++] = n[i++];
		}
		else
		{
			temp[k++] = n[j++];
		}
	}
	while (i <= mid)
	{
		temp[k++] = n[i++];
	}
	while (j <= last)
	{
		temp[k++] = n[j++];
	}
	for (i=0; i<k; i++)
	{
		n[first+i] = temp[i];
	}
}

void m_sort(int n[], int first, int last, int temp[])
{
	if (first < last)
	{
		int mid = (first + last) / 2;
		m_sort(n, first, mid, temp);
		m_sort(n, mid+1, last, temp);
		merge(n, first, mid, last, temp);
	}
}

int main()
{
	int k;
	scanf("%d", &k);
	int *n = (int *)malloc(k*sizeof(int));
	int *temp = (int *)malloc(k*sizeof(int));
	if (!n || !temp)
	{
		exit(1);
	}
	int i;
	for (i=0; i<k; i++)
	{
		scanf("%d", &n[i]);
	}
	m_sort(n, 0, k-1, temp);
	for (i=0; i<k; i++)
	{
		printf("%d ", n[i]);
	}
	printf("n");
	free(n);
	free(temp);
}

输入输出：

5
3 1 2 4 0
0 1 2 3 4

归并排序的时间复杂度是 O(n*log(n))，数据是稳定的