## Ebay Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**In-Person

Lets say each list is of size M

Take list[0],list[1] merge them, take list[2],list[3] merge them,.. take list[n-2],list[n-1] and merge them

Next take two previously sorted list and merge them, keep doing this unil there is one list remaining.

compleixty O(MXN)

or

Merge the list[0] and list[1] call the merged list mergeList

for(i = 2 ; i < n ;i++)

merge(mergeList, list[i])

This is again a O(MXN) algo

```
struct node{
node * next;
int data;
};
node * simple_merge(node * list1, node * list2)
{
node * result = NULL;
node * p1 = list1;
node * p2 = list2;
node * p3 = NULL;
while(p1!=NULL && p2!=NULL)
{
node * chosen = NULL;
if(p2== NULL|| (p1!=NULL && p2->data > p1->data))
{
chosen = p1;
p1 = p1->next;
}
else
{
chosen = p2;
p2 = p2->next;
}
if(result == NULL)
{
result = chosen;
p3 = result;
}
else
{
p3->next = chosen;
p3 = chosen;
}
chosen->next = NULL;
}
return result;
}
node * merge_lists(node ** lists, int numLists)
{
node * result = NULL;
node ** currents = new node * [numLists];
if(numLists == 1)
{
result = lists[0];
}
if(numLists == 2)
{
result=simple_merge(lists[0], lists[1]);
}
else
{
int index = numLists/2;
node * result1= merge_lists(lists, index);
node * result2 = merge_lists(lists[index+1], numLists-index);
result=simple_merge(result1, result2);
}
return result;
}
```

public static Node NmergeSort(LinkedList A[]){

int N= A.length;

Node res=null;

Node node = new Node(null, 0);

while(A.length>0){

int min = Integer.MAX_VALUE;

int I=-1;

for(int i=0;i<N;i++){

if(A[i]!=null && A[i].head.val<min){

min = A[i].head.val;

I=i;

}

}

node = A[I].head;

A[I].head = A[I].head.next;

if(res==null){

res = node;

}else{

node.next=res;

res=node;

}

}

return res;

}

public static Node NmergeSort(LinkedList A[]){

int N= A.length;

Node res=null;

Node node = new Node(null, 0);

while(A.length>0){

int min = Integer.MAX_VALUE;

int I=-1;

for(int i=0;i<N;i++){

if(A[i]!=null && A[i].head.val<min){

min = A[i].head.val;

I=i;

}

}

node = A[I].head;

A[I].head = A[I].head.next;

if(res==null){

res = node;

}else{

node.next=res;

res=node;

}

}

return res;

}

Does the new list has to be sorted as well ? Can u give an example ?

- An Enthusiast April 05, 2014