Re: [code-review] Tie::Array::Sorted

The big thing that strikes me about this module is that the binary
search and insertion sort may be very clever, but it is (in principle)
O(n^2), and (in practice) probably has a large overhead even apart
from the big-O constant.

I would guess that an implementation like the following would probably
be much faster than the current implementation, and also faster than
Tony's idea:

        sub PUSH {
          my ($self, @items) = @_;
          push @{$self->{array}}, @items;
          undef $self->{sorted};
        }

        sub FETCH {
          my ($self, $key) = @_;
          $self->sortme unless $self->{sorted};
          $self->{array}[$key];
        }

        sub sortme {
          my $self = shift;
          my $c = $self->{comparator};
          @{$self->{array}} = sort $c @{$self->{array}};
          $self->{sorted} = 1;
        }

I think this will lose only if there are a *lot* of FETCHes compared
to the number of PUSHes, it might be a little slower, but only a
little.  But I think in general it will win on speed, and it certainly
wins on code size.

You would need to add the ->sortme call to STORE also, but if I were
writing this module I would either do

        sub STORE { croak "Do not.\n" }

or

        *STORE = *PUSH;

---more likely the former.