# Copyright (c) 2023 Yuki Kimoto
# MIT License

class Sort {
  use Comparator::Int;
  use Comparator::Long;
  use Comparator::Float;
  use Comparator::Double;
  use Comparator::String;
  use Comparator;
  use Fn;
  use Array;
  
  static method sort_byte : void ($array : byte[], $comparator : Comparator::Int, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new byte[$length];
    Sort->_sort_byte_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_byte_asc : void ($array : byte[], $offset = 0 : int, $length = -1 : int) {
    &sort_byte($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_byte_desc : void ($array : byte[], $offset = 0 : int, $length = -1 : int) {
    &sort_byte($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_double : void ($array : double[], $comparator : Comparator::Double, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new double[$length];
    Sort->_sort_double_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_double_asc : void ($array : double[], $offset = 0 : int, $length = -1 : int) {
    &sort_double($array, method : int ($a : double, $b : double) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_double_desc : void ($array : double[], $offset = 0 : int, $length = -1 : int) {
    &sort_double($array, method : int ($a : double, $b : double) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_float : void ($array : float[], $comparator : Comparator::Float, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new float[$length];
    Sort->_sort_float_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_float_asc : void ($array : float[], $offset = 0 : int, $length = -1 : int) {
    &sort_float($array, method : int ($a : float, $b : float) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_float_desc : void ($array : float[], $offset = 0 : int, $length = -1 : int) {
    &sort_float($array, method : int ($a : float, $b : float) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_int : void ($array : int[], $comparator : Comparator::Int, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new int[$length];
    Sort->_sort_int_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_int_asc : void ($array : int[], $offset = 0 : int, $length = -1 : int) {
    &sort_int($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_int_desc : void ($array : int[], $offset = 0 : int, $length = -1 : int) {
    &sort_int($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_long : void ($array : long[], $comparator : Comparator::Long, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new long[$length];
    Sort->_sort_long_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_long_asc : void ($array : long[], $offset = 0 : int, $length = -1 : int) {
    &sort_long($array, method : int ($a : long, $b : long) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_long_desc : void ($array : long[], $offset = 0 : int, $length = -1 : int) {
    &sort_long($array, method : int ($a : long, $b : long) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_object : void ($array : object[], $comparator : Comparator, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = Array->new_proto($array, $length);
    
    Sort->_sort_object_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_short : void ($array : short[], $comparator : Comparator::Int, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new short[$length];
    Sort->_sort_short_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  
  static method sort_short_asc : void ($array : short[], $offset = 0 : int, $length = -1 : int) {
    &sort_short($array, method : int ($a : int, $b : int) { return $a <=> $b; }, $offset, $length);
  }
  static method sort_short_desc : void ($array : short[], $offset = 0 : int, $length = -1 : int) {
    &sort_short($array, method : int ($a : int, $b : int) { return $b <=> $a; }, $offset, $length);
  }
  static method sort_string : void ($array : string[], $comparator : Comparator::String, $offset = 0 : int, $length = -1 : int) {
    unless ($array) {
      die "The \$array must be defined";
    }
    
    unless ($comparator) {
      die "The \$comparator must be defined";
    }
    
    unless ($offset >= 0) {
      die "The \$offset must be greater than or equal to 0";
    }
    
    my $array_length = @$array;
    if ($length < 0) {
      $length = $array_length - $offset;
    }
    
    unless ($offset + $length <= $array_length) {
      die "The \$offset + the \$length must be less than or equal to the length of the \$array";
    }
    
    if ($length == 0) {
      return;
    }
    
    my $b = new string[$length];
    Sort->_sort_string_merge_sort($array, $b, $offset, $offset + $length - 1, $length - 1, $comparator);
  }
  static method sort_string_asc : void ($array : string[], $offset = 0 : int, $length = -1 : int) {
    &sort_string($array, method : int ($a : string, $b : string) { return $a cmp $b; }, $offset, $length);
  }
  static method sort_string_desc : void ($array : string[], $offset = 0 : int, $length = -1 : int) {
    &sort_string($array, method : int ($a : string, $b : string) { return $b cmp $a; }, $offset, $length);
  }

  precompile private static method _sort_byte_merge : void($a : byte[], $b : byte[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_byte_merge_sort : void($a : byte[], $b : byte[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_byte_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_byte_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_byte_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_double_merge : void($a : double[], $b : double[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Double) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_double_merge_sort : void($a : double[], $b : double[], $left : int, $right : int, $n : int, $comparator : Comparator::Double){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_double_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_double_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_double_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_float_merge : void($a : float[], $b : float[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Float) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_float_merge_sort : void($a : float[], $b : float[], $left : int, $right : int, $n : int, $comparator : Comparator::Float){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_float_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_float_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_float_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
 precompile  private static method _sort_int_merge : void($a : int[], $b : int[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_int_merge_sort : void($a : int[], $b : int[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_int_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_int_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_int_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_long_merge : void($a : long[], $b : long[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Long) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_long_merge_sort : void($a : long[], $b : long[], $left : int, $right : int, $n : int, $comparator : Comparator::Long){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_long_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_long_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_long_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_object_merge : void($a : object[], $b : object[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator) {
      my $i = $left;
      my $j = $mid + 1;
      my $k = 0;
      while ($i <= $mid && $j <= $right) {
        $i = $left;
        $j = $mid + 1;
        $k = 0;
        while ($i <= $mid && $j <= $right) {
          if ($comparator->($a->[$i], $a->[$j]) <= 0) {
            $b->[$k] = $a->[$i];
            $i++;
          } else {
            $b->[$k] = $a->[$j];
            $j++;
          }
          $k++;
        }
        if ($i == $mid + 1) {
          while ($j <= $right) {
            $b->[$k] = $a->[$j]; 
            $j++;
            $k++;
          }
        } else {
          while($i <= $mid) {
            $b->[$k] = $a->[$i];
            $i++;
            $k++;
          }
        }
      }
      for ($i = 0; $i < $k; $i++) {
        $a->[$i + $left] = $b->[$i];
      }
  }
  
  private static method _sort_object_merge_sort : void($a : object[], $b : object[], $left : int, $right : int, $n : int, $comparator : Comparator){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_object_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_object_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_object_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_short_merge : void($a : short[], $b : short[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::Int) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  private static method _sort_short_merge_sort : void($a : short[], $b : short[], $left : int, $right : int, $n : int, $comparator : Comparator::Int){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
    
    Sort->_sort_short_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_short_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_short_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
  precompile private static method _sort_string_merge : void($a : string[], $b : string[], $left : int, $mid : int, $right : int, $n : int, $comparator : Comparator::String) {
    my $i = $left;
    my $j = $mid + 1;
    my $k = 0;
    while ($i <= $mid && $j <= $right) {
      $i = $left;
      $j = $mid + 1;
      $k = 0;
      while ($i <= $mid && $j <= $right) {
        if ($comparator->($a->[$i], $a->[$j]) <= 0) {
          $b->[$k] = $a->[$i];
          $i++;
        } else {
          $b->[$k] = $a->[$j];
          $j++;
        }
        $k++;
      }
      if ($i == $mid + 1) {
        while ($j <= $right) {
          $b->[$k] = $a->[$j]; 
          $j++;
          $k++;
        }
      } else {
        while($i <= $mid) {
          $b->[$k] = $a->[$i];
          $i++;
          $k++;
        }
      }
    }
    for ($i = 0; $i < $k; $i++) {
      $a->[$i + $left] = $b->[$i];
    }
  }
  
  private static method _sort_string_merge_sort : void($a : string[], $b : string[], $left : int, $right : int, $n : int, $comparator : Comparator::String){
    if ($left >= $right) {
      return;
    }
    
    my $mid = ($left + $right) / 2;
     
    Sort->_sort_string_merge_sort($a, $b, $left, $mid, $n, $comparator);
    Sort->_sort_string_merge_sort($a, $b, $mid + 1, $right, $n, $comparator);
    Sort->_sort_string_merge($a, $b, $left, $mid, $right, $n, $comparator);
  }
  
}