I have to write a C++ program given k sorted lists(or arrays)of numbers and combine them into on sorted array.

Could anyone get me started with an algroithm. I'm stuck, and not sure how or what would be the best way to go about solving this problem.

I have to write a C++ program given k sorted lists(or arrays)of numbers and combine them into on sorted array.
What you are trying to do is actually part of a larger sorting algorithm called "Merge Sort".





here is an example:


http://mathbits.com/MathBits/CompSci/Arr...





You would keep merging the sorted arrays in set K into the "master" sorted array. Thus, you would only be working with two sorted arrays at any one time.





Search the net for "Merge Sort" for other implementations.
Reply:Well, I am not sure if i understand it right. You have an array of numbers and you have to put them in order?





If so, use bubble sort algorithm.





Bubble sort in C++





http://www.24bytes.com/bubble-sort.html
Reply:ALGORITHM:( assuming that u want to sort the lists in increasing order, and your lists are sorted in the inc. order too ):





use k counters, each counter to keep track of the current element being sorted in each array.Then find the minimum of the k numbers currently being processed( each being pointed to by the counter )


then increment the counter which held the location of the min num. repeat the process until all the counters reach the ends of their respective arrays.
Reply:I think your question means you have an unknown number of arrays that you need to combine into one big sorted array, right?





The easiest way is to just combine all the lists into one long list and then sort it.





For example: if you have 5 arrays of 10 items each, just create one big array with 50 items... array1, array2...etc. Just tack one array at the front, then the second, then the third...etc Once you have the whole list, just sort the whole thing using the bubble-sort exodus described above.