NAME

LinkedList::Single::Example::SortedMerge - merge and merge sort on LinkedList::Single lists

SYNOPSIS

use LinkedList::Single::Example::SortedMerge;

my $sorter
= LinkedList::Single::Example::SortedMerge->new
(
    how     => 'copy'                       # or 'relink', the default
  , cmp     => sub( $x, $y ) { $x <=> $y }  # on keys; this is the default
);

my $log     = $sorter->build( [ 3, 'web', 'login' ], [ 8, 'web', 'view' ] );

my $both    = $sorter->merge( $log, $other );       # both consumed

my $sorted  = $sorter->merge_sort( $unsorted );     # use this, not $unsorted
my $also    = $sorter->sort_via_array( $more );     # extract, sort, rebuild

my( $left, $right ) = $sorter->split_half( $list );

DESCRIPTION

An item is a node [ $key, @payload ] of a LinkedList::Single list. merge combines two lists that are each sorted by key into one sorted list; merge_sort sorts a list by splitting it in half, sorting each half and merging them. Both are stable (on equal keys the item from the left goes first) and both consume their arguments, which test false afterwards. sort_via_array takes the items out, sorts them with perl's sort and builds a new list. build and contents put items in and take them out.

There are two merges, chosen by how. copy reads both inputs with cursors and pushes each item onto a new list. relink moves the front node of an input onto the output through Fragments; it reads like a relink but, because a Fragment moves a node's contents into a new array, builds an array per node moved, and it is the slower of the two.

LinkedList::Single::Example::SortedMerge::Array has the same interface over perl arrays and is the test oracle with perl's sort: the tests merge and sort the same random items through all of them and compare.

How it is benchmarked

benchmarks/50-SortedMerge/compare sorts 1,000, 10,000 and 100,000 random numbers with both list merge sorts, the array merge sort, sort_via_array, perl's sort and the module's own $list->sort; times the growth of the module's sort from 500 to 8,000 items; merges two sorted lists of n/2; and reports the memory of a merged result and statements and branches in each merge. benchmarks/50-SortedMerge/raw-nodes looks inside the list's nodes, which no other example does, to measure a pointer merge sort: the ceiling that only code inside the module can reach.

Why it matters

Merging is the step under a merge sort, and under combining ordered logs or files. On a linked list the textbook merge relinks nodes and copies nothing. Through this module's public operations it does not: at every size measured the array merge and perl's sort are faster, and the list merge sorts are 13 to 50 times slower than the array one. The example did find that the module's own sort was quadratic, and the pointer merge sort that replaced it now beats the array merge sort written in perl. The measurements and references are in LinkedList::Single::Example::SortedMerge::POD.

SEE ALSO

LinkedList::Single::Example::SortedMerge::POD, LinkedList::Single::Example::SortedMerge::Array, LinkedList::Single