The first thing I noticed is an error in your script that would stop it from working correctly (albeit nothing to do with the sort order problem):

$multiple   = floor($multiple); #round down to int    } else {
[download]

That '} else {' does nothing, since it comes after a comment; as a result, all of your "$number"s and "$multiple"s get set to their default values, which is probably not what you want. Just move that clause down to the next line; i.e., it should read

...
        $multiple = $length / $number;
        $multiple   = floor($multiple);
    } else {
        $number = 1;
        $multiple = $length;
    }
...
[download]

As for the rest of it, I just faked up a bit of a script to test this and fed it a "slice" of the sort you're talking about, and it came out sorted. Example:

#!/usr/bin/perl
use warnings;
use strict;
use POSIX qw/ceil floor/;

my $len = shift or die "Need a MAX_LENGTH argument\n";

sub split_Slices {
  my ($slice_big,$max_length,$overlap)=@_;
  my @out;

  for my $slice (@$slice_big){
    my ($start, $length, $end, $multiple, $number) = ($slice->{begin},
+ $slice->{length});

    if($max_length && ($length > $overlap)) {
        $number = ceil(($length-$overlap) / ($max_length-$overlap));
        $multiple = floor($length / $number);
    } else {
        $number = 1;
        $multiple = $length;
    }

    for(my $i=0; $i < $number; $i++) {
      $end = $start + $multiple + $overlap;
      push @out, { begin => $start, end => $end };
      $start += $multiple + 1;
    }
  }

  return \@out;
}

my @stuff;
push @stuff, { begin => $_ * 10, length => 10 } for 0..9;

my $ret = split_Slices(\@stuff, $len, 0);
use Data::Dumper;
print Dumper($ret);
[download]

Running it with a couple of different arguments produces the following:

./slicer 10
$VAR1 = [
          {
            'begin' => 0,
            'end' => 10
          },
          {
            'begin' => 10,
            'end' => 20
          },
          {
            'begin' => 20,
            'end' => 30
          },
          {
            'begin' => 30,
            'end' => 40
          },
          {
            'begin' => 40,
            'end' => 50
          },
          {
            'begin' => 50,
            'end' => 60
          },
          {
            'begin' => 60,
            'end' => 70
          },
          {
            'begin' => 70,
            'end' => 80
          },
          {
            'begin' => 80,
            'end' => 90
          },
          {
            'begin' => 90,
            'end' => 100
          }
        ];
[download]

./slicer 5
$VAR1 = [
          {
            'begin' => 0,
            'end' => 5
          },
          {
            'begin' => 6,
            'end' => 11
          },
          {
            'begin' => 10,
            'end' => 15
          },
          {
            'begin' => 16,
            'end' => 21
          },
          {
            'begin' => 20,
            'end' => 25
          },
          {
            'begin' => 26,
            'end' => 31
          },
          {
            'begin' => 30,
            'end' => 35
          },
          {
            'begin' => 36,
            'end' => 41
          },
          {
            'begin' => 40,
            'end' => 45
          },
          {
            'begin' => 46,
            'end' => 51
          },
          {
            'begin' => 50,
            'end' => 55
          },
          {
            'begin' => 56,
            'end' => 61
          },
          {
            'begin' => 60,
            'end' => 65
          },
          {
            'begin' => 66,
            'end' => 71
          },
          {
            'begin' => 70,
            'end' => 75
          },
          {
            'begin' => 76,
            'end' => 81
          },
          {
            'begin' => 80,
            'end' => 85
          },
          {
            'begin' => 86,
            'end' => 91
          },
          {
            'begin' => 90,
            'end' => 95
          },
          {
            'begin' => 96,
            'end' => 101
          }
        ];
[download]

So it seems that the sorting part of it works fine (although I'd take a closer look at that overlap routine.) Perhaps you should examine the data being fed to it.

-- 
Education is not the filling of a pail, but the lighting of a fire.
 -- W. B. Yeats