Tie::Quicksort::Lazy - a lazy quicksort with tiearray interface

  use Tie::Quicksort::Lazy TRIVIAL => 1023;
  tie my @producer, Tie::Quicksort::Lazy, @input;
  while (@producer){
    my $first_remaining = shift @producer;
    ...
  };

  use sort 'stable';
  tie my @StableProducer, Tie::Quicksort::Lazy, \&comparator,  @input;
  ...

A pure-perl lazy, stable, quicksort. The only defined way to access the resulting tied array is with shift.

Sorting is deferred until an item is required.

Stability is maintained by choosing a pivot element randomly and treating equal elements differently in the before and after sections.

This module operates on a copy of the input array, which becomes the initial partition. As the partitions are divided, the old partitions are let go.

For a stable variant, tie to Tie::Quicksort::Lazy::Stable instead and use a stable perl sort for the trivial sort or set "TRIVIAL" to 1 on the use line.

when the first parameter is an unblessed coderef, that coderef will be used as the sort comparison function. The default is

   sub { $_[0] cmp $_[1] }

Ergo, if you want to use this module to sort a list of coderefs, you will need to bless the first one.

A variable $trivial is defined which declares the size of a partition that we simply hand off to Perl's sort for sorting. by default, this is no longer used, but it is still available if you want it.

this module was inspired by an employment interview question concerning the quicksort-like method of selecting the first k from n items ( see http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting )

0.01

Original version; created by h2xs 1.23 with options

  -ACX
	-b
	5.6.1
	-n
	Tie::Quicksort::Lazy

0.02

revised to use perl arrays for partitioning operations instead of a confusing profusion of temporary index variables

0.04

revised internal data structure, no longer using perl's sort for anything by default, no longer scrambling input due to random pivot element selection.

Tie::Array::Sorted::Lazy is vaguely similar

David L. Nicol davidnico@cpan.org

Copyright (C) 2009 by the author

This library is free software; you may redistribute and/or modify it under the same terms as Perl.