Parallel sorting of a singly-linked list

Question

Is there any algorithm that makes it parallel sorting of a linked list worth it?

It's well known that Merge Sort is the best algorithm to use for sorting a linked list.

Most merge sorts are explained in terms of arrays, with each half recursively sorted. This would make it trivial to parallelize: sort each half independently then merge the two halves.

But a linked list doesn't have a "half-way" point; a linked list goes until it ends:

Head → [a] → [b] → [c] → [d] → [e] → [f] → [g] → [h] → [i] → [j] → ...

The implementation i have now walks the list once to get a count, then recursively splits the counts until we're comparing a node with it's NextNode. The recursion takes care of remembering where the two halves are.

This means the MergeSort of a linked list progresses linearly through the list. Since it seems to demand linearly progression through a list, i would think it then cannot be parallelized. The only way i could imagine it is by:

• walk the list to get a count O(n)
• walk half the list to get to the halfway point O(n/2)
• then sort each half O(n log n)

But even if we did parallelize sorting (a,b) and (c,d) in separate threads, i would think that the false sharing during NextNode reordering would kill any virtue of parallelization.

Is there any parallel algorithms for sorting a linked list?

Array merge sort algorithm

Here is the standard algorithm for performing a merge sort on an array:

algorithm Merge-Sort
    input:
        an array, A (the values to be sorted)
        an integer, p (the lower bound of the values to be sorted)
        an integer, r (the upper bound of the values to be sorted)

    define variables:
        an integer, q (the midpoint of the values to be sorted)

    q ← ⌊(p+r)/2⌋
    Merge-Sort(A, p, q)   //sort the lower half
    Merge-Sort(A, q+1, r) //sort the upper half   
    Merge(A, p, q, r)     

This algorithm is designed, and meant, for arrays, with arbitrary index access. To make it suitable for linked lists, it has to be modified.

Linked-list merge sort algorithm

This is (single-threaded) singly-linked list, merge sort, algorithm i currently use to sort the singly linked list. It comes from the Gonnet + Baeza Yates Handbook of Algorithms

algorithm sort:
    input:
        a reference to a list, r (pointer to the first item in the linked list)
        an integer, n (the number of items to be sorted)
    output:
        a reference to a list (pointer to the sorted list)

    define variables:
        a reference to a list, A (pointer to the sorted top half of the list)
        a reference to a list, B (pointer to the sorted bottom half of the list)
        a reference to a list, temp (temporary variable used to swap)

    if r = nil then
        return nil

    if n > 1 then
        A ← sort(r, ⌊n/2⌋ )
        B ← sort(r, ⌊(n+1)/2⌋ )
        return merge( A, B )

    temp ← r
    r ← r.next
    temp.next ← nil
    return temp

A Pascal implementation would be:

function MergeSort(var r: list; n: integer): list;
begin
   if r = nil then 
       Result := nil
   else if n > 1 then
      Result := Merge(MergeSort(r, n div 2), MergeSort(r, (n+1) div 2) )
   else
   begin
      Result := r;
      r := r.next;
      Result.next := nil;
   end
end;

And if my transcoding works, here's an on-the-fly C# translation:

list function MergeSort(ref list r, Int32 n)
{
   if (r == null)
      return null;

    if (n > 1)
    {
       list A = MergeSort(r, n / 2);
       list B = MergeSort(r, (n+1) / 2);
       return Merge(A, B);
    }
    else
    {
       list temp = r;
       r = r.next;
       temp.next = null;
       return temp;
    }
}

What i need now is a parallel algorithm to sort a linked list. It doesn't have to be merge sort.

Some have suggested copying the next n items, where n items fit into a single cache-line, and spawn a task with those.

Sample data

algorithm GenerateSampleData
    input:
        an integer, n (the number of items to generate in the linked list)
    output:
        a reference to a node (the head of the linked list of random data to be sorted)

    define variables:
        a reference to a node, head (the returned head)
        a reference to a node, item (an item in the linked list)
        an integer, i (a counter)

    head ← new node
    item ← head        

    for i ← 1 to n do
        item.value ← Random()
        item.next ← new node
        item ← item.next

    return head

So we could generate a list of 300,000 random items by calling:

head := GenerateSampleData(300000);

Benchmarks

Time to generate 300,000 items    568 ms

MergeSort 
    count splitting variation   3,888 ms (baseline)

MergeSort
    Slow-Fast midpoint finding  3,920 ms (0.8% slower)

QuickSort
    Copy linked list to array       4 ms
    Quicksort array             5,609 ms
    Relink list                     5 ms
    Total                       5,625 ms (44% slower)

Bonus Reading

• Stackoverflow: What's the fastest algorithm for sorting a linked list?
• Stackoverflow: Merge Sort a Linked List
• Mergesort For Linked Lists
• Parallel Merge Sort O(log n) pdf, 1986
• Stackoverflow: Parallel Merge Sort (Closed, in typical SO nerd-rage fashion)
• Parallel Merge Sort Dr. Dobbs, 3/24/2012
• Eliminate False Sharing Dr. Dobbs, 3/14/2009

Answer 1

Mergesort is perfect for parallel sorting. Split the list in two halves and sort each of them in parallel, then merge the result. If you need more than two parallel sorting processes, do so recursively. If you don't happen to have infinitely many CPUs, you can omit parallelization at a certain recusion depth (which you will have to determine by testing).

BTW, the usual approach to splitting a list in two halves of roughly the same size is Floyd's Cycle Finding algorithm, also known as the hare and tortoise approach:

Node MergeSort(Node head)
{
   if ((head == null) || (head.Next == null))
      return head; //Oops, don't return null; what if only head.Next was null

   Node firstHalf = head;
   Node middle = GetMiddle(head);
   Node secondHalf = middle.Next;
   middle.Next = null; //cut the two halves

   //Sort the lower and upper halves
   firstHalf = MergeSort(firstHalf);
   secondHalf = MergeSort(secondHalf);

   //Merge the sorted halves 
   return Merge(firstHalf, secondHalf);
}

Node GetMiddle(Node head)
{
   if (head == null || head.Next == null)
       return null;

   Node slow = head;
   Node fast = head;
   while ((fast.Next != null) && (fast.Next.Next != null))
   {
       slow = slow.Next;
       fast = fast.Next.Next;
   }
   return slow;
}

After that, list and list2 are two lists of roughly the same size. Concatenating them would yield the original list. Of course, fast = fast->next->next needs further attention; this is just to demonstrate the general principle.