2つの並べ替えられた配列を新しい配列に並べ替える

タイトル:両方の配列list 1とlist 2が昇順配列であることが知られており、例えば{1,3,34100},{2,23,45,67200300}である.まず、新しい配列でこの2つの配列を含み、昇順に並べて、時間の複雑さをできるだけ低くする必要があります.
 
解法:2つのポインタで配列1と配列2の最初の要素をそれぞれ指し、2つの要素を比較させ、小さな要素を新しい配列に入れ、小さな要素の配列のポインタを1を加えて移動させる.2つの配列の要素を比較し、そのうちの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)であることがわかる.