CareerCup

merge(int a[], int m,int b[], int n, int c[])
{
	int *aptr=a, *bptr=b, *cptr=c;
	while(aptr <= (a+m) && bptr <= (b+n))
	{
		if(*aptr <= *bptr)
		{
			*cptr = *aptr++;
			while((aptr <= a+m) && *cptr == *aptr)
				aptr++;
			while((bptr <= b+n) &&*cptr == *bptr)
				bptr++;
			cptr++;
		}else
		if (*aptr < *bptr)
		{
			*cptr = *aptr++;
			while(aptr <= (a+m) && *captr == *(aptr))
				aptr++;
			cptr++;
		}else
		if (*bptr < *aptr)
		{
			*cptr = *bptr++;
			while(bptr <= (b+n) && *cptr == *(bptr))
				bptr++;
			cptr++;
			
		}
	}
		--cptr;
		if( aptr > (a+m))
			while(bptr <= (bptr+n))
			{
				if (*cptr != *bptr )
					++*cptr = *bptr;
				bptr++; 
			}
		if (bptr > (b+n))
			while (aptr <= (aptr+m))
			{
				if (*cptr != *aptr )
					++*cptr = *aptr;
				aptr++;
			}
/* print the Array C till cptr */
}

Worst case TC : (m+n) SC : O(m+n)

Use TreeSet

// merge smallest item from each list until both lists are exhausted
// two SPECIAL_CASEs to take care of:
//  1. values are equal as we come across them
//  2. trying to add a value already on the list

int[] merge(int[] a, int a_size, int[]b, int b_size)
{
  // make a new integer array, sized large enough to handle all unique items
  int result[] = new int[a_size + b_size];

  int pos_a = 0;
  int pos_b = 0;

  while (!(pos_a == a_size && pos_b == a_size))  // run until out of items on both arrays
  {
    if (pos_a == a_size)      { push(result, b[pos_b]); pos_b++; continue; }  // a is out of items
    if (pos_b == b_size)      { push(result, a[pos_a]); pos_a++; continue; }  // b is out of items
    if (a[pos_a] == b[pos_b]) { push(result, a[pos_a]); pos_a++; pos_b++; continue; } // SPECIAL_CASE: items are equal, so only add one
    if (a[pos_a] < b[pos_b])  { push(result, a[pos_a]); pos_a++; continue; }  // a is smaller
    if (a[pos_a] > b[pos_b])  { push(result, b[pos_b]); pos_b++; continue; }  // b is smaller
  }
}

void push(int[] a, int value)
{
  static int lastElement = 0;
  if (a[lastElement] == value) { return; }   // SPECIAL_CASE: watch out for already added items
  a[lastElement++] = value;
}

public static int[] arraySortAndMinimize(int[] a, int[] b) {
		TreeSet tree = new TreeSet();
		int[] answer;
		for (int i= 0; i<a.length; i++) {tree.add(a[i]);}
		for (int i= 0; i<b.length; i++) {tree.add(b[i]);} 
		answer = new int[tree.size()];
		int count = 0;
		for (Object value : tree) {answer[count] = ((Integer)value).intValue(); count++;}
		return answer;
	}

public int[] Merge(int[] a1, int[] a2)
{
	int[] result = new int[a1.Length + a2.Length];
	int i = 0;
	int j = 0;
	int k = 0;

	while (i < a1.Length || j < a2.Length)
	{
		int n;
		if (i < a1.Length && j < a2.Length)
		{
			if (a1[i] < a2[j])
			{
				n = a1[i];
				i++;
			}
			else
			{
				n = a2[j];
				j++;
			}
		}
		else if (i < a1.Length)
		{
			n = a1[i];
			i++;
		}
		else
		{
			n = a2[j];
			j++;
		}

		result[k] = n;
		k++;

		while (i < a1.Length && a1[i] == n)
			i++;
		while (j < a2.Length && a2[j] == n)
			j++;
	}

	if (k < (a1.Length + a2.Length))
	{
		var tmp = new int[k];
		Array.Copy(result, tmp, k);
		result = tmp;
	}

	return result;
}