The London Perl and Raku Workshop takes place on 26th Oct 2024. If your company depends on Perl, please consider sponsoring and/or attending.

# NAME

Algorithm::SISort - Select And Insert sorting algorithm

# SYNOPSIS

``````  use Algorithm::SISort qw(Sort Sort_inplace);

@sorted_list = Sort {\$_[0] <=> \$_[1]} @unsorted_list;
# ... or ...
\$number_of_comparisons = Sort_inplace {\$_[0] <=> \$_[1]} @unsorted_list;``````

# DESCRIPTION

This module implements a sorting algorithm I saw in BIT 28 (1988) by István Beck and Stein Krogdahl. This implementation is mainly intended to try out the Inline module by Brian Ingerson. The algorithm is a combination of Straight Insertion Sort and Selection Sort. While Insertion Sort and Selection Sort both are of complexity O(n**2), Select and Insert Sort should have complexity O(n**1.5).

This module defines the functions `Sort` and `Sort_inplace`, which have signatures similar to the internal `sort` function. The difference is that a codref defining a comparison is always required and that the two values to compare are always passed in `@_` and not as `\$a` and `\$b`. (Although I might change that later.)

`Sort` returns a sorted copy if the array, but `Sort_inplace` sorts the array in place (as the name suggests) and returns the number of comparisons done. (Note that the sorting is always done in place, `Sort` just copies the array before calling the internal sort routine.)

# BUGS

Bug-reports are very welcome on the CPAN Request Tracker at:

``    http://rt.cpan.org/NoAuth/Bugs.html?Dist=Algorithm-SISort``

Inline, Inline::C, and A Select And Insert Sorting Algorithm by István Beck and Stein Krogdahl in BIT 28 (1988), 726-735.