i am trying to creat a program in C++ that will read in 3 sorted files(with 15 interger values each), use the merge sort with linked lists, and output a new file. how would i do this?
Printable View
i am trying to creat a program in C++ that will read in 3 sorted files(with 15 interger values each), use the merge sort with linked lists, and output a new file. how would i do this?
merge sort for single linked list:
merge sort merges sorted partitions from smallest of 2 to whole range (incremention is power of two (2,4,8...)
You can start by running trough the list and comparing each second partition with the one following it and swap them as needed. To merge larger partitions you have these special cases:
first.last > second.first : just link em up
second.first > first.last : link em up in inverse order
otherways run trough first or last until you hit the other, linking up each item, then start linking up from both sides until one of them ends, and lastly link the rest of the remaining partition.
when you have reached last loop, where only big two partitions are left, take into account that the second will be of size: total-firstpartitionsize