Q:

Reducing time complexity in Perl arrays

I am having a array 
[3, 1, 2, 5, 4, 6]

I want to sort ( Changed sort to arranging in a certain pattern) this as : Move to right and replace the index with next highest integer on right side. Say in this array 3 is replaced by 5, 1 is replaced by 2 and so on..
I want the output as 
[5, 2, 5, 6, 6, 6]

Algorithm :

Start a forloop. It will iterate till last element
Starting from first index it will match with next index and compare the value
If second index is less than first then move to third index
If not change the first index with second index
Try with all the indexes

It is a normal algorithm. But the time complexity is n*n. (No exactly n*n). 
Is there a way to reduce the complexity. Because in case of large arrays, it would be very slow. Can somebody provide me algorithm for time complexity n.
Adding code
use strict;
use warnings;

my @arr1 = qw/3 1 2 5 4 6/;
my @arr2;
my ($j, $i);
for($i = 0; $i <= $#arr1; $i++) {
    $j = $i;
    while ( $j < $#arr1) {
        if ( $arr1[$i] < $arr1[$j+1]) {
            push @arr2,$arr1[$j+1];
            last;
        } 
        if ($i == $#arr1) {
            push @arr2,$arr1[$j];
        }
        $j++;
    }

}
push @arr2, $arr1[$#arr1];   ## Pushing the last array index

print @arr2;

Output:
525666

A:

Your current algorithm can touch one position multiple times, which is inefficient. By the power of recursion, we could do better. Imagine a function that performs your sort until it finds a number higher than some $n:
[3, 1, 2, 5, 4, 6] # start here
#^
[3, 1, 2, 5, 4, 6] # look at next number. It's smaller, so we recurse
#^--^
[3, 1, 2, 5, 4, 6] # in recursion: look at next number, replace
#^  ^--^
#|__|
[3, 2, 2, 5, 4, 6] # return new index. It's smaller, so we recurse
#^     ^
#|_____|
[3, 2, 2, 5, 4, 6] # in recursion: look at next number, replace
#^     ^--^
#|_____|
[3, 2, 5, 5, 4, 6] # return new index
#^        ^
#|________|
[3, 2, 5, 5, 4, 6] # It's larger, so we replace and go to new index
#^--------^
[5, 2, 5, 5, 4, 6] # Look at next number. It's smaller, so we recurse
#         ^--^
[5, 2, 5, 5, 4, 6] # In recursion: replace
#         ^  ^--^
#         |__|
[5, 2, 5, 5, 6, 6] # return new index
#         ^     ^
#         |_____|
[5, 2, 5, 5, 6, 6] # It's larger, so we replace. Go to new index
#         ^-----^
[5, 2, 5, 6, 6, 6] # Done!

The difficult part is to write a function that does this. As we want to write a recursive function, we have to think backwards:

[] – empty array (no indices left) sorts to itself
[6] – array with single element left sorts to that element
[4, 6] → [6, 6] – if the element at the next index is larger, copy it over and the new index is at the next element
[5, 4, ...] – if the next element is smaller, recurse at that index.

Example implementation:
sub weird_sort {
  my ($array, $start, $return) = @_;
  $start //= 0;
  my $next = $start + 1;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      return $next if $return;  # return index to higher levels so that they
                                # can check whether the $next elem is larger.
      $start = $next;
      $next  = $start + 1;
    }
    else {
      $next = weird_sort($array, $next, 1);
    }
  }

  return $next;
}

# called in-place like
weird_sort(\@array);

The next step would be to remove the recursion:
sub weird_sort {
  my ($array) = @_;
  my ($start, $next) = (0, 1);

  my @stack;

  while ($next <= $#$array) {
    # check if one is larger
    if ($array->[$start] < $array->[$next]) {
      $array->[$start] = $array->[$next];
      ($start, $next) = @stack ? (pop(@stack), $next) : ($next, $next + 1);
    }
    else {
      push @stack, $start;
      ($start, $next) = ($next, $next + 1);
    }
  }
}

This seems to work for simple cases, but I'm not entirely certain that this is a general solution.

