Administrace komentářů

Ještě bych dodal, jen tak z prdele, co s tím, kdyby to muselo být efektivní a kdyby to náhodou nesmělo využívat řídká pole v Bashi. #firstworldproblems #becausewecan

Napřed si vyrobíme mergesort na integery:

mergesort() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -r -i size="${#input_reference[@]}"
  local -a -i merge runs indices
  local -i index previous merged_idx \
           run_a_idx run_a_stop \
           run_b_idx run_b_stop

  output_reference=("${input_reference[@]}")
  if ((size == 0)); then return; fi

  previous=output_reference[0]
  runs=(0)
  for ((index = 0;;)) do
    for ((++index;; ++index)); do
      if ((index >= size)); then break 2; fi
      if ((output_reference[index] < previous)); then break; fi
      previous=output_reference[index]
    done
    previous=output_reference[index]
    runs+=(index)
  done
  runs+=(size)

  while (("${#runs[@]}" > 2)); do
    indices=("${!runs[@]}")
    merge=("${output_reference[@]}")
    for ((index = 0; index < "${#indices[@]}" - 2; index += 2)); do
      merged_idx=runs[indices[index]]
      run_a_idx=merged_idx
      previous=indices[$((index + 1))]
      run_a_stop=runs[previous]
      run_b_idx=runs[previous]
      run_b_stop=runs[indices[$((index + 2))]]
      unset runs[previous]
      while ((run_a_idx < run_a_stop && run_b_idx < run_b_stop)); do
        if ((merge[run_a_idx] < merge[run_b_idx])); then
          output_reference[merged_idx++]=merge[run_a_idx++]
        else
          output_reference[merged_idx++]=merge[run_b_idx++]
        fi
      done
      while ((run_a_idx < run_a_stop)); do
        output_reference[merged_idx++]=merge[run_a_idx++]
      done
      while ((run_b_idx < run_b_stop)); do
        output_reference[merged_idx++]=merge[run_b_idx++]
      done
    done
  done
}

sort_by_number_after_last_slash() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -a -i input output
  local -a input_map
  local item

  for item in "${input_reference[@]}"; do
    input_map["${item##*/}"]="${item}"
  done
  input=("${!input_map[@]}")
  mergesort input output  # na hovno
  echo "${input[@]}"
  echo "${output[@]}"
  output_reference=()
  for item in "${output[@]}"; do
    output_reference+=("${input_map[item]}")
  done
}

declare -a -i unsorted=(RANDOM RANDOM RANDOM RANDOM RANDOM)
declare -a -i sorted
mergesort unsorted sorted
echo "${unsorted[@]}"
echo "${sorted[@]}"