两个排好序的数组重新排序为一个新数组

题目：已知两个数组list1和list2都为升序排列，例如{1， 3， 34， 100}，{2， 23， 45， 67， 200，300}。先要求用一个新数组包含这两个数组，并且按升序排列，时间复杂度尽量低。

解法：用两个指针分别指向数组一和数组二的第一个元素，让两个元素进行比较，把较小元素放进新数组中，并使较小元素的数组的指针加1后移。在让两个数组的元素进行比较，直到其中一个数组遍历完毕，把另一个数组的剩下的元素直接放到新数组的后面即可。

c语言代码

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

typedef struct
{
	int data[MAXSIZE];
	int length; 
}SqList;

int main()
{
	void sortElem(SqList List1, SqList List2, SqList *ResList);
	SqList List1, List2;
	List1.length = 5;
	for (int i = 0; i < List1.length; i++)
	{
		scanf("%d", &List1.data[i]);
	}
	
	List2.length = 6;
	for (int j = 0; j < List2.length; j++)
	{
		scanf("%d", &List2.data[j]);
	}
	
	SqList * ResList = (SqList *)malloc(sizeof(SqList));
	sortElem(List1, List2, ResList);
	for (int i = 0; i < ResList->length; i++)
	{
		printf("%d
", ResList->data[i]);
	}
}

void sortElem(SqList List1, SqList List2, SqList *ResList) 
{
	int i = 0, j = 0, k = 0;
	int len1 = List1.length;
	int len2 = List2.length;
	while (i < len1 && j < len2)
	{
		if (List1.data[i] <= List2.data[j])
		{
			ResList->data[k] = List1.data[i];
			i++;
		}
		else
		{
			ResList->data[k] = List2.data[j];
			j++;
		}
		k++;	
	}
	if (i == len1)
	{
		while (j < len2)
		{
			ResList->data[k] = List2.data[j];
			k++;
			j++;
		}
	} 
	if (j == len2)
	{
		while (i < len1)
		{
			ResList->data[k] = List1.data[i];
			k++;
			i++;
		};
	}
	ResList->length = k;
}

由以上代码可看出，时间复杂度为O(N)