There's been some interesting suggestions by my fellow Monks that will work in all cases, specifically when you don't have control over access to the array (eg being changed by a module).

However, if you have got control over access, wrap it all up as a class:

package My::Array::Sorted;

my $changed = 0;

sub new {
    my ( $class, @data ) = @_;
    my $self = bless [], $class;
    $self->push( @data );
    return $self;
}

sub sort {
    my $self = shift;
    @$self = sort @$self
        if $changed;
    $changed = 0;
}

sub push {
    my $self = shift;
    push @$self, @_;
    $changed = 1;
}

sub change {
    my ( $self, $index, $value ) = @_;
    $self->[$index] = $value;
    $changed = 1;
}

sub show {
    my $self = shift;
    print join( ", ", $self->get() ), "\n";
}

package main;

my $array = My::Array::Sorted->new( 5, 4, 3, 2, 1 );

$array->show();
$array->push( 10, 12, 14, 13, 11 );
$array->show();
$array->change( 3, 55 );
$array->show();
[download]

You might have to change or add some methods; it all depends on your intended use.