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]

Give a man a fish:  <%-{-{-{-<

In reply to Re^4: Why does my get_max_index function return zero? (High Water Mark Algorithm) by AnomalousMonk
in thread Why does my get_max_index function return zero? (High Water Mark Algorithm) by hghosh

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.