Sorting question -- One pass algo

Given n sorted lists of integers as file input, write a one-pass algorithm that produces one sorted file of output, where the output is the sorted merger of the n input files.

I was thinking of using Merge sort , but its complexity is O(nlogn).
What do you guys suggest?
How can I apply one-pass algo on n sorted list of integers??
Suggest some strategy that will give me a kick to start.

1) You check the (i)th element of each list, and input them to the new list in the desired order
2) Do step (1) untill all lists run out of elements :D

Quote:

---

Originally Posted by Gseries

I was thinking of using Merge sort , but its complexity is O(nlogn).
What do you guys suggest?
How can I apply one-pass algo on n sorted list of integers??

---

You don't need merge sort as you are just merging ;)

@GReaper -thnx 4 replyin

hhmm... I understand there are lot of lists.
Say List 1, list 2, list 3, list 4....
Each list is having different no. of elements inside it.

say list 1 has 50, list 2 has 25 , list 3 has 100 , so on...

I didn't get you when u said check for (i th) element?
what does i th means??

Quote:

---

Originally Posted by Gseries

I didn't get you when u said check for (i th) element?
what does i th means??

---

Well, think of how the merge operation used in merge sort works. Now, suppose that the list (e.g., an array) has an odd number of elements. Clearly, the two partitions of the list will then be of different sizes. Does the merge still work? Why?

Basically, the whole idea behind this is to extend this same merge operation to work on n lists.

Quote:

---

Originally Posted by Gseries

I didn't get you when u said check for (i th) element?
what does i th means??

---

Like 1st, 2nd, 3rd, 4th ... (i)th :D

Quote:

---

Originally Posted by GReaper

Like 1st, 2nd, 3rd, 4th ... (i)th :D

---

checking the i th element of all the lists won't make it one-pass .
One pass would be somewhat visiting the element only once.

Depends on what you are talking about. Let's say you have 3 lists:x, y, z. You basically do:

Code:

---

for each element in x y z
    compare x[i], y[j], z[k]
    put smallest element in output list //lets say y[j]
    increment index of element added //in this case j
repeat

---

Each element is only visited once with this basic merge. Note: Your initial assumption was that each list was already sorted.

Quote:

---

Originally Posted by laserlight

Well, think of how the merge operation used in merge sort works. Now, suppose that the list (e.g., an array) has an odd number of elements. Clearly, the two partitions of the list will then be of different sizes. Does the merge still work? Why?

Basically, the whole idea behind this is to extend this same merge operation to work on n lists.

---

Thanks . I understand Merge sort.
My main issue that is coming is how can i combine the elements by only visiting them once.

Quote:

---

Originally Posted by Gseries

checking the i th element of all the lists won't make it one-pass .
One pass would be somewhat visiting the element only once.

---

I meant compare the (i)th elements of the lists, each element will be visited only one.

EDIT: Think of it this way

Code:

---

for (int i = 0; i < size; i++){
    mergedArray[i*4] = array1[i];
    mergedArray[i*4+1] = array2[i];
    mergedArray[i*4+2] = array3[i];
    mergedArray[i*4+3] = array4[i];

    sort(mergedArray+i*4, 4);
}

---

Or something like that... :D

Use a priority queue (heap) of lists where each item contains both the file pointer and the next unprocessed item from the file (for ordering).
Then merge!