CareerCup

Why would one union two sorted arrays in memory utilizing multiple core's (or even worse one core with multiple threads) to achieve that? The bottle neck is clearly memory and not CPU.
Did he tell the two sets were on different machines? Did he potentially want to start a discussion about when multi threading makes sense (in parctice I've seen lots and lots of multithreading approaches due to a lack of understanding on overlapped I/O and other concepts)?
Especially in Java, I can't imagine doing anything good in multi-threading that task. A different thing is multiple arrays on multiple machines. That's more interesting.

find the median of the two sorted arrays. Divide the two arrays based on values greater and larger than the median. Merge the two distinct sets on two threads. Merge is straightforward = result(thread1).Append(result(thread2))

Use mergesort with Java ForkJoin. This way each thread will receive a slice of each array and sort it, after the subsequent sorts and merges the final array will be sorted.

Here's a sample code I found on the internet:

Mergesort

import java.lang.reflect.Array;
 
public class MergeSort {
 public static <T extends Comparable<? super T>> void sort(T[] a) {
  @SuppressWarnings("unchecked")
  T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);
  mergesort(a, helper, 0, a.length-1);
 }
  
 private static <T extends Comparable<? super T>> void mergesort(T[] a, T[] helper, int lo, int hi){
  if (lo>=hi) return;
  int mid = lo + (hi-lo)/2;
  mergesort(a, helper, lo, mid);
  mergesort(a, helper, mid+1, hi);
  merge(a, helper, lo, mid, hi);  
 }
 
 private static <T extends Comparable<? super T>> void merge(T[] a, T[] helper, int lo, int mid, int hi){
  for (int i=lo;i<=hi;i++){
   helper[i]=a[i];
  }
  int i=lo,j=mid+1;
  for(int k=lo;k<=hi;k++){
   if (i>mid){
    a[k]=helper[j++];
   }else if (j>hi){
    a[k]=helper[i++];
   }else if(isLess(helper[i], helper[j])){
    a[k]=helper[i++];
   }else{
    a[k]=helper[j++];
   }
  }
 }
 
 private static <T extends Comparable<? super T>> boolean isLess(T a, T b) {
  return a.compareTo(b) < 0;
 }
}

The Task:

private static class MergeSortTask<T extends Comparable<? super T>> extends RecursiveAction{
 private static final long serialVersionUID = -749935388568367268L;
 private final T[] a;
 private final T[] helper;
 private final int lo;
 private final int hi;
  
 public MergeSortTask(T[] a, T[] helper, int lo, int hi){
  this.a = a;
  this.helper = helper;
  this.lo = lo;
  this.hi = hi;
 }
 @Override
 protected void compute() {
  if (lo>=hi) return;
  int mid = lo + (hi-lo)/2;
  MergeSortTask<T> left = new MergeSortTask<>(a, helper, lo, mid);
  MergeSortTask<T> right = new MergeSortTask<>(a, helper, mid+1, hi);
  invokeAll(left, right);
  merge(this.a, this.helper, this.lo, mid, this.hi);
   
   
 }
 private void merge(T[] a, T[] helper, int lo, int mid, int hi){
  for (int i=lo;i<=hi;i++){
   helper[i]=a[i];
  }
  int i=lo,j=mid+1;
  for(int k=lo;k<=hi;k++){
   if (i>mid){
    a[k]=helper[j++];
   }else if (j>hi){
    a[k]=helper[i++];
   }else if(isLess(helper[i], helper[j])){
    a[k]=helper[i++];
   }else{
    a[k]=helper[j++];
   }
  }
 }
 private boolean isLess(T a, T b) {
  return a.compareTo(b) < 0;
 }
}

And finally a wrapper method that will do all the job behind the scenes:

public static <T extends Comparable<? super T>> void sort(T[] a) {
 @SuppressWarnings("unchecked")
 T[] helper = (T[])Array.newInstance(a[0].getClass() , a.length);
 ForkJoinPool forkJoinPool = new ForkJoinPool(10);
 forkJoinPool.invoke(new MergeSortTask<T>(a, helper, 0, a.length-1));
}

You can delete all the code inside `MergeSort` class, leave only the private class, and it will still work the same ;)

What about using something similar to bitonic sort and doing the comparisons in parallel processors.

For Union of 2 sorted arrays
Create 2 threads
One thread keep adds elements from the beginning
Other thread adds elements from the ending.
Stop adding elements till both points meet in the final array.