Merge sort - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Merge sort

lobbwilllobbwill Posts: 3Member
Hi all, i'm new to algorithms and to this forum but was wondering if anyone has an algorithm which uses a merge sort to sort three sorted sequences into one?

Any help would be much appreciated. Thanks in advance

Comments

  • zibadianzibadian Posts: 6,349Member
    : Hi all, i'm new to algorithms and to this forum but was wondering if
    : anyone has an algorithm which uses a merge sort to sort three sorted
    : sequences into one?
    :
    : Any help would be much appreciated. Thanks in advance

    Here is a simplified algorithm to merge 3 sorted lists. It is not the merge sort, because that's a full sorting algorithm, not just a way to merge sorted lists.
    [code]
    outList MergeLists (inListArray) {

    // Loop until all lists are empty

    while (length inListArray > 0) {
    int small = 0;

    // First find smallest item in all the lists

    for (i = 0 ; i < length inListArray; i++) {
    if (inListArray[i][0] < inListArray[small][0])
    small = i;
    }

    // Then add that item into the result list and remove it from the source list

    move inListArray[small][0] to outList

    // Finally check if that list becomes empty

    if (length inListArray[small] = 0) {
    remove inListArray[small] from inListArray
    }
    }
    }
    [/code]
    This code runs in O(n) time, where n is the number of total items.
  • lobbwilllobbwill Posts: 3Member
    Thank you very much for your help with this! As I say i'm very new to algorithms and am trying to answer a few questions so am just about to make another post and would be great if you could help!

    Many thanks
Sign In or Register to comment.