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

//prototipo da funcao:
void merge(int *lista1,int *lista2,int *lista3,int tam1,int tam2);

void main(void){
int t1, t2, t3; //os tamanhos das listas.
int *l1, *l2, *l3; // os ponteiros para as listas.
int i;

//Neste ponto deve-se fazer o preenchimento das listas, 
//como voce quiser. 
//Faca t1 e t2 conterem os tamanhos da lista1 e 
//da lista2, respectivamente.

printf("Qual o tamanho da primeira lista? ");
scanf("%d",&t1);

printf("Qual o tamanho da segunda lista? ");
scanf("%d",&t2);

l1=(int*)malloc(t1*sizeof(int));
if(l1==NULL){
	printf("%s\n","Erro de alocacao de memoria");
	return; //sai do programa
}

l2=(int*)malloc(t2*sizeof(int));
if(l2==NULL){
	printf("%s\n","Erro de alocacao de memoria");
	return; //sai do programa
}

printf("Entre com os numeros da primeira lista:\n");
for(i=0;i<t1;i++){
	scanf("%d",&l1[i]);
}

printf("Entre com os numeros da segunda lista:\n");
for(i=0;i<t2;i++){
	scanf("%d",&l2[i]);
}

t3=t1+t2;

l3=(int*)malloc(t3*sizeof(int));
if(l3==NULL){
	printf("%s\n","Erro de alocacao de memoria");
	return; //sai do programa
}

merge(l1,l2,l3,t1,t2);

printf("Lista resultante:\n");
for(i=0;i<t3;i++){
	printf("%d\n",l3[i]);
}

}//fim main()

void merge(int *lista1,int *lista2,int *lista3,int tam1,int tam2)
{
int tam3;
int i,j,k;
int final;

tam3=tam1+tam2;

final=0;
for(i=0,j=0,k=0;k<tam3;k++){
	if(final==1){
		lista3[k]=lista2[j];
		j++;
	}
	if(final==2){
		lista3[k]=lista1[i];
		i++;
	}
	if(final==0){
		if(lista1[i]<lista2[j]){
			lista3[k]=lista1[i];
			i++;
			if(i==tam1)final=1;
		}
		else{
			lista3[k]=lista2[j];
			j++;
			if(j==tam2)final=2;
		}
	}

}
}//fim merge()