sorting - リンクされたリストの自然なマージソート

Question

しばらくの間、自然なマージソートの実装 (リンクされたリスト) を探していましたが、運がありませんでした。

リンクされたリストのマージソート

ここには、再帰的な実装と反復的な実装の両方がありますが、これを自然なマージソートに変換する方法がわかりません。

最良のケースでO(n)の複雑さを得るために実行を確認するにはどうすればよいですか? C/C++ である必要はなく、任意の言語または疑似コードでもかまいません。

ありがとうございました。

Answer 1

これはF#での私の試みです。参照用の通常のマージソートの実装:

// Sorts a list containing elements of type T.  Takes a comparison
// function comp that takes two elements of type T and returns -1
// if the first element is less than the second, 0 if they are equal,
// and 1 if the first element is greater than the second.
let rec sort comp = function 
| []  -> []  // An empty list is sorted
| [x] -> [x] // A single element list is sorted
| xs  ->
    // Split the list in half, sort both halves,
    // and merge the sorted halves.
    let half = (List.length xs) / 2
    let left, right = split half xs
    merge comp (sort comp left) (sort comp right)

今度はナチュラルバージョンに挑戦。これは、最良の場合は O(n) になりますが、最良の場合は、入力リストが逆順でソートされている場合です。

let rec sort' comp ls =

    // Define a helper function.  Streaks are stored in an accumulator.
    let rec helper accu = function
    | [] -> accu 
    | x::xs -> 
        match accu with
        // If we are not in a streak, start a new one
        | [] -> helper [x] xs 

        // If we are in a streak, check if x continues
        // the streak.
        | y::ys -> 
            if comp y x > 0 

            // x continues the streak so we add it to accu
            then helper (x::y::ys) xs

            // The streak is over. Merge the streak with the rest
            // of the list, which is sorted by calling our helper function on it.
            else merge comp accu (helper [x] xs)

    helper [] ls

二度目の試み。これは、最良のケースでも O(n) になります。最良のケースは、入力リストが既にソートされている場合です。比較機能を無効にしました。ソートされたリストは逆順で構築されるため、最後に逆順にする必要があります。

let rec sort'' comp ls =
    // Flip the comparison function
    let comp' = fun x y -> -1 * (comp x y)
    let rec helper accu = function
    | [] -> accu
    | x::xs -> 
        match accu with
        | [] -> helper [x] xs
        | y::ys -> 
            if comp' y x > 0 
            then helper (x::y::ys) xs
            else merge comp' accu (helper [x] xs)

    // The list is in reverse sorted order so reverse it.
    List.rev (helper [] ls)

Answer 2

自然なマージソートが何であるかはわかりませんが、リンクリストのマージソートは次のように記述します。

【Javaのコード】

// Merge sort the linked list.
// From min to max.
// Time complexity = O(nlgn).
public static Node mergeSortLLFromMinToMax (Node head) {
    if (head == null || head.next == null) return head; // No need to sort.
    // Get the mid point of this linked list.
    Node prevSlower = head;
    Node slower = head;
    Node faster = head;
    while (faster != null && faster.next != null) {
        prevSlower = slower;
        slower = slower.next;
        faster = faster.next.next;
    }
    // Cut of the main linked list.
    prevSlower.next = null;

    // Do recursion.
    Node left = mergeSortLLFromMinToMax (head);
    Node right = mergeSortLLFromMinToMax (slower);

    // Merge the left and right part from min to max.
    Node currHead = new Node ();
    Node tempCurrHead = currHead;
    while (left != null && right != null) {
        if (left.data <= right.data) {
            // Add the elem of the left part into main linked list.
            tempCurrHead.next = left;
            left = left.next;
        } else {
            // Add the elem of the right part into main linked list.
            tempCurrHead.next = right;
            right = right.next;
        }
        tempCurrHead = tempCurrHead.next;
    }
    if (left != null) {
        // Add the remaining part of left part into main linked list.
        tempCurrHead.next = left;
        left = left.next;
        tempCurrHead = tempCurrHead.next;
    } else if (right != null) {
        // Add the remaining part of right part into main linked list.
        tempCurrHead.next = right;
        right = right.next;
        tempCurrHead = tempCurrHead.next;
    }

    return currHead.next;
}

Answer 3

ウィキペディアには疑似コードの実装があります:

 # Original data is on the input tape; the other tapes are blank
 function mergesort(input_tape, output_tape, scratch_tape_C, scratch_tape_D)
     while any records remain on the input_tape
         while any records remain on the input_tape
             merge( input_tape, output_tape, scratch_tape_C)
             merge( input_tape, output_tape, scratch_tape_D)
         while any records remain on C or D
             merge( scratch_tape_C, scratch_tape_D, output_tape)
             merge( scratch_tape_C, scratch_tape_D, input_tape)

 # take the next sorted chunk from the input tapes, and merge into the single given output_tape.
 # tapes are scanned linearly.
 # tape[next] gives the record currently under the read head of that tape.
 # tape[current] gives the record previously under the read head of that tape.
 # (Generally both tape[current] and tape[previous] are buffered in RAM ...)
 function merge(left[], right[], output_tape[])
     do
        if left[current] ≤ right[current]
            append left[current] to output_tape
            read next record from left tape
        else
            append right[current] to output_tape
            read next record from right tape
    while left[current] < left[next] and right[current] < right[next]
    if left[current] < left[next]
        append current_left_record to output_tape
    if right[current] < right[next]
        append current_right_record to output_tape
    return