mhk said:
Hi ,
is there any way to merge three sorted arrays into a sorted file,
without using 4th array. i guess 3 way merge sort is the only option but
i dont know its algorithem.
can anyone tell me algorithm of 3 way merge sort or anyother way to
solve this problem in c++ or c .
Thank you veryyyyy much.
Here is one I just cooked up. It's a classic merge sort - there are way
more efficient algorithms.
template <
typename container_type,
typename iterator_iterator0,
typename iterator_iterator1void merge_sort(
container_type & output,
iterator_iterator0 iterator0_start,
iterator_iterator0 iterator0_end,
iterator_iterator1 iterator1_start,
iterator_iterator1 iterator1_end
) {
while (
( iterator0_start != iterator0_end )
&& ( iterator1_start != iterator1_end )
) {
if ( * ( iterator0_start ) < * ( iterator1_start ) )
{
output.push_back( * ( iterator0_start ++ ) );
}
else
{
output.push_back( * ( iterator1_start ++ ) );
}
}
if ( iterator0_start == iterator0_end )
{
while (
( iterator1_start != iterator1_end )
) {
output.push_back( * ( iterator1_start ++ ) );
}
}
else
{
while (
( iterator0_start != iterator0_end )
) {
output.push_back( * ( iterator0_start ++ ) );
}
}
}
template <
typename container_type,
typename iterator_iterator0,
typename iterator_iterator1,
typename iterator_iterator2void merge_sort(
container_type & output,
iterator_iterator0 iterator0_start,
iterator_iterator0 iterator0_end,
iterator_iterator1 iterator1_start,
iterator_iterator1 iterator1_end,
iterator_iterator2 iterator2_start,
iterator_iterator2 iterator2_end
)
{
while (
( iterator0_start != iterator0_end )
&& ( iterator1_start != iterator1_end )
&& ( iterator2_start != iterator2_end )
) {
if ( * ( iterator0_start ) < * ( iterator1_start ) )
{
if ( * ( iterator0_start ) < * ( iterator2_start ) )
{
output.push_back( * ( iterator0_start ++ ) );
}
else
{
output.push_back( * ( iterator2_start ++ ) );
}
}
else
{
if ( * ( iterator1_start ) < * ( iterator2_start ) )
{
output.push_back( * ( iterator1_start ++ ) );
}
else
{
output.push_back( * ( iterator2_start ++ ) );
}
}
}
if ( iterator0_start == iterator0_end )
{
merge_sort(
output,
iterator1_start,
iterator1_end,
iterator2_start,
iterator2_end
);
}
else if ( iterator1_start == iterator1_end )
{
merge_sort(
output,
iterator0_start,
iterator0_end,
iterator2_start,
iterator2_end
);
}
else // if ( iterator2_start == iterator2_end )
{
merge_sort(
output,
iterator0_start,
iterator0_end,
iterator1_start,
iterator1_end
);
}
}
#include <list>
#include <algorithm>
#include <iostream>
#include <iterator>
int main()
{
std::list<int> int_list0;
std::list<int> int_list1;
std::list<int> int_list2;
std::list<int> out;
int_list0.push_back( 1 );
int_list0.push_back( 6 );
int_list0.push_back( 11 );
int_list0.push_back( 15 );
int_list1.push_back( 0 );
int_list1.push_back( 5 );
int_list1.push_back( 10 );
int_list1.push_back( 15 );
int_list2.push_back( 7 );
int_list2.push_back( 8 );
int_list2.push_back( 9 );
int_list2.push_back( 15 );
int array[] = { 4 , 5, 6, 88 };
merge_sort(
out,
int_list0.begin(),
int_list0.end(),
int_list1.begin(),
int_list1.end(),
array + 0,
array + (sizeof(array)/sizeof(*array))
);
copy(out.begin(), out.end(), std:
stream_iterator<int>(std::cout,
" "));
}
