bash merge sort

bash merge sort


bash归并排序

#!/bin/bash
rest() { shift; echo $@; }
length() { echo $#; }
first() { echo $1; }
merge()
{
  declare left=$1 right=$2 result=
  declare length_left=$(length $left)
  declare length_right=$(length $right)
  while (( length_left>0 || length_right>0 )); do
    if (( length_left>0 && length_right>0 )); then
      if [ $(first $left) -le $(first $right) ]; then
        result="$result $(first $left)"
        left=$(rest $left)
      else
        result="$result $(first $right)"
        right=$(rest $right)
      fi
    elif [ $(length $left) -gt 0 ]; then
      result="$result $(first $left)"
      left=$(rest $left)
    elif [ $(length $right) -gt 0 ]; then
      result="$result $(first $right)"
      right=$(rest $right)
    fi
    length_left=$(length $left)
    length_right=$(length $right)
  done
  echo $result
}
merge_sort()
{
  [ $# -le 1 ] && { echo $@; return; }
  declare -i middle=$(($#/2+1))
  declare left= right= result=
  for ((i=1;i<middle;i++)); do
    left="$left ${!i}"
  done
  for ((i=middle;i<=$#;i++)); do
    right="$right ${!i}"
  done
  left=$(merge_sort $left)
  right=$(merge_sort $right)
  result=$(merge "$left" "$right")
  echo $result
}
merge_sort $@

执行：

# ./merge_sort.sh $(for in in {1..50}; do echo $((RANDOM%200-100)); done)
-99 -89 -88 -84 -83 -83 -81 -76 -75 -70 -70 -70 -54 -53 -51 -51 -49 -49 -40 -40 -30 -27 -24 -19 -15 -13 -12 -12 -8 -2 -2 -2 2 4 10 17 20 24 28 34 39 39 40 42 45 48 48 49 62 83

算法参考：Merge sort


-fin-