I have been looking for a natural mergesort implementation (linked lists) for a while now but had no luck.
Here we have both, the recursive and the iterative implementation but I don't know how to turn this into a natural mergesort.
How do I check for the runs to get O(n) complexity in the best case? It does not have to be C/C++, can be any language or even Pseudocode.
Thank you.
There's a pseudocode implementation on Wikipedia:
# 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
This is my attempt in F#. An implementation of regular merge sort for reference:
// 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)
Now an attempt at the natural version. This will be O(n) in the best case, but the best case is when the input list is in reverse sorted order.
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
A second attempt. This will also be O(n) in the best case, where the best case is now when the input list is already sorted. I negated the comparison function. The sorted list will be built up in reversed order so you need to reverse it at the end.
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)
I am not sure what is the natural merge sort , but merge sort for linked list, I write like this:
[Code in 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;
}
My very raw implementation of the algorithm using C#
public static class LinkedListSort
{
public static DataStructures.Linear.LinkedListNode<T> Sort<T>(DataStructures.Linear.LinkedListNode<T> firstNode) where T : IComparable<T>
{
if (firstNode == null)
throw new ArgumentNullException();
if (firstNode.Next == null)
return firstNode;
var head = firstNode;
var leftNode = head;
int iterNum = 0;
while (leftNode != null)
{
//Let's start again from the begining
leftNode = head;
iterNum = 0;
DataStructures.Linear.LinkedListNode<T> tailNode = null;
while (leftNode != null)
{
//Let's get the left sublist
//Let's find the node which devides sublist into two ordered sublists
var sentinelNode = GetSentinelNode(leftNode);
var rightNode = sentinelNode.Next;
//If the right node is null it means that we don't have two sublist and the left sublist is ordered already
//so we just add the rest sublist to the tail
if (rightNode == null)
{
if (tailNode == null)
break;
tailNode.Next = leftNode;
break;
}
sentinelNode.Next = null;
//Let's find the node where the right sublist ends
sentinelNode = GetSentinelNode(rightNode);
var restNode = sentinelNode.Next;
sentinelNode.Next = null;
DataStructures.Linear.LinkedListNode<T> newTailNode = null;
//Merging of two ordered sublists
var mergedList = Merge(leftNode, rightNode, ref newTailNode);
//If we're at the beginning of the list the head of the merged sublist becomes the head of the list
if (iterNum == 0)
head = mergedList;
else //add the
tailNode.Next = mergedList;
tailNode = newTailNode;
leftNode = restNode;
iterNum++;
}
if (iterNum == 0)
break;
}
return head;
}
/// <summary>
/// Merges two ordered sublists
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="aNode">Left part of sublist</param>
/// <param name="bNode">Right part of sublist</param>
/// <param name="tailNode">Tail node of the merged list</param>
/// <returns>The result of merging</returns>
private static DataStructures.Linear.LinkedListNode<T> Merge<T>(DataStructures.Linear.LinkedListNode<T> leftNode,
DataStructures.Linear.LinkedListNode<T> rightNode,
ref DataStructures.Linear.LinkedListNode<T> tailNode) where T : IComparable<T>
{
var dummyHead = new DataStructures.Linear.LinkedListNode<T>();
var curNode = dummyHead;
while (leftNode != null || rightNode != null)
{
if (rightNode == null)
{
curNode.Next = leftNode;
leftNode = leftNode.Next;
}
else if (leftNode == null)
{
curNode.Next = rightNode;
rightNode = rightNode.Next;
}
else if (leftNode.Value.CompareTo(rightNode.Value) <= 0)
{
curNode.Next = leftNode;
leftNode = leftNode.Next;
}
else
{
curNode.Next = rightNode;
rightNode = rightNode.Next;
}
curNode = curNode.Next;
}
tailNode = curNode;
return dummyHead.Next;
}
/// <summary>
/// Returns the sentinel node
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="firstNode"></param>
/// <returns></returns>
private static DataStructures.Linear.LinkedListNode<T> GetSentinelNode<T>(DataStructures.Linear.LinkedListNode<T> firstNode) where T : IComparable<T>
{
var curNode = firstNode;
while (curNode != null && curNode.Next != null && curNode.Value.CompareTo(curNode.Next.Value) <= 0)
curNode = curNode.Next;
return curNode;
}
}
