class Array
  def mergesort(&cmp)
    if cmp == nil
      cmp = lambda { |a, b| a <=> b }
    end
    if size <= 1
      self.dup
    else
       halves = split.map{ |half|
        half.mergesort(&cmp)
      }
      merge(*halves, &cmp)
    end
  end

 
  protected
  def split
    n = (length / 2).floor - 1
    [self[0..n], self[n+1..-1]]
  end

  def merge(first, second, &predicate)
    result = []
    until first.empty? || second.empty?
     if predicate.call(first.first, second.first) <= 0
        result << first.shift
      else
        result << second.shift
      end 
    end
    result.concat(first).concat(second)
  end
end

class Array
  def stable_sort
    n = 0
    c = lambda { |x| n+= 1; [x, n]}
    if block_given?
      sort { |a, b|
        yield(c.call(a), c.call(b))        
      }
    else
      sort_by &c
    end
  end
end

export PATH="$(/usr/sbin/sysctl -n user.cs_path)"

export IFS=$'\n'
#export IFS=$' \t\n'

ar1=('g h c' abc def 123)
ar2=('1 2 3' ABC ghc DEF)
ar3=('-x' '! & ?' $'a test\nsentence' $'another test\nsentence\n.' a64bitapp a32bitapp)

printf "%s\n" "${#ar1[@]}" "${#ar2[@]}" "${#ar3[@]}"  


# ar3
for ((i=0; i < "${#ar3[@]}"; i++)); do echo "${ar3[$i]}"; done | sort | nl
for ((i=0; i < "${#ar3[@]}"; i++)); do echo ${ar3[$i]}; done | sort | nl
for ((i=0; i < "${#ar3[@]}"; i++)); do echo "${ar3[$i]}" | ruby -0777 -n -e 'p $_.to_s'; done | nl
for ((i=0; i < "${#ar3[@]}"; i++)); do printf -- "${ar3[$i]}\n" | ruby -0777 -n -e 'p $_.to_s'; done | nl


# sort a single array
ar3sorted=( $(for ((i=0; i < "${#ar3[@]}"; i++)); do echo ${ar3[$i]}; done | sort) )
for ((i=0; i < "${#ar3sorted[@]}"; i++)); do echo "${ar3sorted[$i]}" | ruby -0777 -n -e 'p $_.to_s'; done | nl
for ((i=0; i < "${#ar3sorted[@]}"; i++)); do printf "%s\n" "${ar3sorted[$i]}" | ruby -0777 -n -e 'p $_.to_s'; done | nl


# adding \000\n as array item delimiter
printf "%s\000\n" "${ar3[@]}"  | sed -n -e 'l'
printf "%s\000\n" "${ar3[@]}"  | ruby -n -e 'p $_.to_s'
printf "%s\000\n" "${ar3[@]}"  | ruby -0777 -n -e 'p $_.to_s'
printf "%s\000\n" "${ar3[@]}" | sed -e :a -e '$!N; s/\n/NEWLINE/g; ta' | ruby -n -e 'p $_.to_s'
printf "%s\000\n" "${ar3[@]}" | sed -e :a -e '$!N; s/\n/NEWLINE/g; ta' | tr '\000' '\n' | sed -e 's/^NEWLINE//' | ruby -n -e 'p $_.to_s'


ar3sorted=( $(printf "%s\000\n" "${ar3[@]}" | sed -e :a -e '$!N; s/\n/NEWLINE/g; ta' | tr '\000' '\n' | sed -e 's/^NEWLINE//' | sort) )
for ((i=0; i < "${#ar3sorted[@]}"; i++)); do printf -- "${ar3sorted[$i]//NEWLINE/\n}" | ruby -0777 -n -e 'p $_.to_s'; done | nl


# sort multiple arrays; convert embedded newline characters into single spaces
ar4=( $(printf "%s\n\000" "${ar1[@]}" "${ar2[@]}" "${ar3[@]}" | tr '\n' ' ' | tr '\000' '\n' | sort) )

# sort multiple arrays; preserve embedded newline characters as NEWLINE
ar4=( $(printf "%s\000\n" "${ar1[@]}" "${ar2[@]}" "${ar3[@]}" | sed -e :a -e '$!N; s/\n/NEWLINE/g; ta' | tr '\000' '\n' | sed -e 's/^NEWLINE//' | sort) )


printf "%s\n" "${#ar4[@]}"  
printf "%s\n" "${ar4[@]}" | nl  

for ((i=0; i < "${#ar4[@]}"; i++)); do echo ${ar4[$i]//NEWLINE/\\n}; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do echo -e ${ar4[$i]//NEWLINE/\\n}; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do printf -- ${ar4[$i]//NEWLINE/\\n}"\n"; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do printf -- "${ar4[$i]//NEWLINE/\n}\n"; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do printf "%s\n" ${ar4[$i]//NEWLINE/\\n}; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do printf -- "${ar4[$i]//NEWLINE/\n}\n" | ruby -0777 -n -e 'p $_.to_s'; done | nl
for ((i=0; i < "${#ar4[@]}"; i++)); do printf "%s\n" "${ar4[$i]//NEWLINE/\n}" | ruby -0777 -n -e 'p $_.to_s'; done | nl

rpm -qa --queryformat="%{size} %{name}-%{version}-%{release}\n" | sort -rn | less

cities = Array.new
cities << { :name => 'SPb',    :year => 1703, :population => 5_000_000 }
cities << { :name => 'Moscow', :year => 1147, :population => 10_000_000_000 }

cities.sort_by { |city| city[:year] }.each do |city|
  puts "#{city[:name]}"
end

class Array
  def stable_sort
    n = 0
    sort_by {|x| n+= 1; [x, n]}
  end
end

ps axu | sort -rn | more