FWIW, here's a GRT (decorate-sort-undecorate) approach, but still O(n log n):

c:\@Work\Perl\monks>perl -wMstrict -le
"use Test::More 'no_plan';
 use Test::NoWarnings;
 ;;
 use List::Util qw(shuffle);
 ;;
 use constant RA       => shuffle -4 .. 4;
 use constant RA_MAX_I => $#{[ RA ]};
 ;;
 for my $i_ins (0 .. RA_MAX_I+1) {
   my @rb = ((RA)[ 0 .. $i_ins-1 ], 99, (RA)[ $i_ins .. RA_MAX_I ]);
   my ($i_max) =
     map unpack('x[N] N', $_),
     reverse sort
     map pack('N N', 0x7fff_ffff+$rb[$_], $_),
     0 .. $#rb
     ;
   ok $i_ins == $i_max, qq{largest at (@rb)[$i_ins]};
   }
 ;;
 done_testing;
"
ok 1 - largest at (99 -1 -2 4 1 -3 2 3 0 -4)[0]
ok 2 - largest at (-1 99 -2 4 1 -3 2 3 0 -4)[1]
ok 3 - largest at (-1 -2 99 4 1 -3 2 3 0 -4)[2]
ok 4 - largest at (-1 -2 4 99 1 -3 2 3 0 -4)[3]
ok 5 - largest at (-1 -2 4 1 99 -3 2 3 0 -4)[4]
ok 6 - largest at (-1 -2 4 1 -3 99 2 3 0 -4)[5]
ok 7 - largest at (-1 -2 4 1 -3 2 99 3 0 -4)[6]
ok 8 - largest at (-1 -2 4 1 -3 2 3 99 0 -4)[7]
ok 9 - largest at (-1 -2 4 1 -3 2 3 0 99 -4)[8]
ok 10 - largest at (-1 -2 4 1 -3 2 3 0 -4 99)[9]
1..10
ok 11 - no warnings
1..11
[download]

I like to plant binary trees:

Edit: for inserting it does a lot more comparisons than a linear search does for searching. For finding min and max there are no comparisons, just traversal. It's use is when one wants to search repeatedly the tree. I have added a search() to the code (30min after).

Edit: after 8hrs, fixed synopsis' testing of min/max, there was a comparator mishap ([0]<=>[1] instead of [1]<=>[0]))!

use My::Bintree;

my $T = My::Bintree->new(3, sub { return $_[0] <=> $_[1] });
$T->add(5);
$T->add(2);
$T->add(8);
$T->add(8);
$T->add(8);
print "maxi: ".join(",",$T->maxi())."\nmini: ".join(",",$T->mini())."\
+n";
print "searched for number 8: ".join(",", $T->search(8))."\n";
# maxi: 8 8 8
# mini: 2
# searched for number 8: 8,8,8

# or add complex data, e.g. (x,y) points and compare their distance fr
+om origin
$T = My::Bintree->new(
    # a first point:
    [1,2],
    # the comparator:
    sub { return $_[0]->[0]**2 + $_[0]->[1]**2 <=> $_[1]->[0]**2 + $_[
+1]->[1]**2 }
);
$T->add([3,8]);
$T->add([5,5]);
$T->add([3,4]);
$T->add([3,2]);
$T->add([3,6]);
$T->add([2,3]);
$T->add([3,2]);
$T->add([2,1]);
print "furthest point(s): ".join(',', map { '(x: '.$_->[0].', y: '.$_-
+>[1].')' } $T->maxi())."\n";
print "nearest  point(s): ".join(',', map { '(x: '.$_->[0].', y: '.$_-
+>[1].')' } $T->mini())."\n";
print "searched for points with same distance from origin as point (2,
+3): ".join(',', map { '(x: '.$_->[0].', y: '.$_->[1].')' } $T->search
+([2,3]))."\n";

# furthest point(s): (x: 3, y: 8)
# nearest  point(s): (x: 1, y: 2),(x: 2, y: 1)
# searched for points with same distance from origin as point (2,3): (
+x: 3, y: 2),(x: 2, y: 3),(x: 3, y: 2)

# here is how you find the max index (and value) of an array
# even if there are several max/min values
my @arr = (3,4,5,100,4,5,100,100, 0, 1, 2);
# the comparator must return -1 if 1st arg < 2nd arg!!! (re: edit abov
+e)
$T = My::Bintree->new([0, shift @arr], sub { $_[0]->[1] <=> $_[1]->[1]
+ });
$T->add([$_,$arr[$_]]) for 0..$#arr;
print "max: ".join(',', map { '(index: '.$_->[0].', value: '.$_->[1].'
+)' } $T->maxi())."\n";
print "min: ".join(',', map { '(index: '.$_->[0].', value: '.$_->[1].'
+)' } $T->mini())."\n";
print "searched for value of 5: ".join(',', map { '(index: '.$_->[0].'
+, value: '.$_->[1].')' } $T->search([undef,5]))."\n";

# max: (index: 2, value: 100),(index: 5, value: 100),(index: 6, value:
+ 100)
# min: (index: 7, value: 0)
# searched for value of 5: (index: 1, value: 5),(index: 4, value: 5)
[download]

The package and tests:

Read more... (13 kB)

bw, bliako