Jak posortować tablicę w Bash

Mam tablicę w Bash, na przykład:

array=(a c b f 3 5)

Muszę posortować tablicę. Nie tylko wyświetlając zawartość w posortowany sposób, ale aby uzyskać nową tablicę z posortowanymi elementami. Nowa posortowana tablica może być zupełnie nową lub starą.

Naprawdę nie potrzebujesz całego kodu:

IFS=$'\n' sorted=($(sort <<<"${array[*]}"))
unset IFS

Obsługuje spacje w elementach (o ile nie jest to nowa linia) i działa w Bash 3.x.

na przykład:

$ array=("a c" b f "3 5")
$ IFS=$'\n' sorted=($(sort <<<"${array[*]}")); unset IFS
$ printf "[%s]\n" "${sorted[@]}"
[3 5]
[a c]
[b]
[f]

Uwaga: @sorontar wskazał, że należy zachować ostrożność, jeśli elementy zawierają symbole wieloznaczne, takie jak *lub ?:

Część posortowana = ($ (...)) używa operatora „split and glob”. Powinieneś wyłączyć glob: set -flub set -o nogloblub shopt -op nogloblub element tablicy, taki jak, *zostanie rozszerzony do listy plików.

Co się dzieje:

Rezultatem jest sześć rzeczy, które dzieją się w podanej kolejności:

1. IFS=$'\n'
2. "${array[*]}"
3. <<<
4. sort
5. sorted=($(...))
6. unset IFS

Po pierwsze IFS=$'\n'

Jest to ważna część naszej operacji, która wpływa na wynik 2 i 5 w następujący sposób:

Dany:

• "${array[*]}" rozwija się do każdego elementu rozdzielanego pierwszym znakiem IFS
• sorted=() tworzy elementy dzieląc się na każdy znak IFS

IFS=$'\n' ustawia rzeczy w taki sposób, że elementy są rozwijane przy użyciu nowej linii jako separatora, a następnie tworzone w taki sposób, że każda linia staje się elementem. (tj. Dzielenie w nowej linii).

Ograniczanie przez nową linię jest ważne, ponieważ tak sortdziała (sortowanie według linii). Dzielenie tylko nową linią nie jest tak ważne, ale jest potrzebne, aby zachować elementy zawierające spacje lub tabulatory.

Wartością domyślną IFSjest spacja , tabulator , po którym następuje nowy wiersz , i byłoby to nieodpowiednie dla naszej operacji.

Następnie sort <<<"${array[*]}"część

<<<, nazywany tutaj ciągami , pobiera rozwinięcie "${array[*]}", jak wyjaśniono powyżej, i przekazuje je na standardowe wejście sort.

W naszym przykładzie sortjest podawany następujący ciąg:

a c
b
f
3 5

Od sort swego rodzaju produkuje:

3 5
a c
b
f

Następnie sorted=($(...))część

$(...)Część, zwana na zmianę polecenia powoduje jego zawartość ( sort <<<"${array[*]}), w celu działania jako normalne polecenia podczas stosowania otrzymanego standardowe wyjście jako dosłownym który przechodzi gdziekolwiek $(...)jest.

W naszym przykładzie daje to coś podobnego do zwykłego pisania:

sorted=(3 5
a c
b
f
)

sorted następnie staje się tablicą utworzoną przez podzielenie tego literału na każdy nowy wiersz.

Wreszcie unset IFS

Spowoduje to zresetowanie wartości IFSdo wartości domyślnej i jest to po prostu dobra praktyka.

Ma to na celu zapewnienie, że nie będziemy powodować problemów z czymkolwiek, na czym polega IFSpóźniej w naszym skrypcie. (W przeciwnym razie musielibyśmy pamiętać, że zmieniliśmy rzeczy - coś, co może być niepraktyczne w przypadku złożonych skryptów).

Oryginalna odpowiedź:

array=(a c b "f f" 3 5)
readarray -t sorted < <(for a in "${array[@]}"; do echo "$a"; done | sort)

wynik:

$ for a in "${sorted[@]}"; do echo "$a"; done
3
5
a
b
c
f f

Uwaga ta wersja radzi sobie z wartościami zawierającymi znaki specjalne lub spacje ( z wyjątkiem nowych linii)

Uwaga readarray jest obsługiwany w bash 4+.

Edytuj Na podstawie sugestii @Dimitre zaktualizowałem go do:

readarray -t sorted < <(printf '%s\0' "${array[@]}" | sort -z | xargs -0n1)

który ma tę zaletę, że nawet zrozumie sortowanie elementów z prawidłowo osadzonymi znakami nowej linii. Niestety, jak poprawnie zasygnalizował @ruakh, nie oznaczało to, że wynik readarraybędzie poprawny , ponieważ readarraynie ma opcji użycia NULzamiast zwykłych znaków nowej linii jako separatorów linii.

Oto czysta implementacja quicksort Bash:

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
qsort() {
   local pivot i smaller=() larger=()
   qsort_ret=()
   (($#==0)) && return 0
   pivot=$1
   shift
   for i; do
      if (( i < pivot )); then
         smaller+=( "$i" )
      else
         larger+=( "$i" )
      fi
   done
   qsort "${smaller[@]}"
   smaller=( "${qsort_ret[@]}" )
   qsort "${larger[@]}"
   larger=( "${qsort_ret[@]}" )
   qsort_ret=( "${smaller[@]}" "$pivot" "${larger[@]}" )
}

Użyj jako np.

$ array=(a c b f 3 5)
$ qsort "${array[@]}"
$ declare -p qsort_ret
declare -a qsort_ret='([0]="3" [1]="5" [2]="a" [3]="b" [4]="c" [5]="f")'

Ta implementacja jest rekurencyjna… więc oto iteracyjne szybkie sortowanie:

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
qsort() {
   (($#==0)) && return 0
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if [[ "${qsort_ret[i]}" < "$pivot" ]]; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

W obu przypadkach możesz zmienić kolejność, z której korzystasz: użyłem porównań ciągów, ale możesz użyć porównań arytmetycznych, porównać czas modyfikacji pliku wrt itp. Po prostu użyj odpowiedniego testu; możesz nawet uczynić go bardziej ogólnym i poprosić go o użycie pierwszego argumentu, którym jest funkcja testowa, np.

#!/bin/bash

# quicksorts positional arguments
# return is in array qsort_ret
# Note: iterative, NOT recursive! :)
# First argument is a function name that takes two arguments and compares them
qsort() {
   (($#<=1)) && return 0
   local compare_fun=$1
   shift
   local stack=( 0 $(($#-1)) ) beg end i pivot smaller larger
   qsort_ret=("$@")
   while ((${#stack[@]})); do
      beg=${stack[0]}
      end=${stack[1]}
      stack=( "${stack[@]:2}" )
      smaller=() larger=()
      pivot=${qsort_ret[beg]}
      for ((i=beg+1;i<=end;++i)); do
         if "$compare_fun" "${qsort_ret[i]}" "$pivot"; then
            smaller+=( "${qsort_ret[i]}" )
         else
            larger+=( "${qsort_ret[i]}" )
         fi
      done
      qsort_ret=( "${qsort_ret[@]:0:beg}" "${smaller[@]}" "$pivot" "${larger[@]}" "${qsort_ret[@]:end+1}" )
      if ((${#smaller[@]}>=2)); then stack+=( "$beg" "$((beg+${#smaller[@]}-1))" ); fi
      if ((${#larger[@]}>=2)); then stack+=( "$((end-${#larger[@]}+1))" "$end" ); fi
   done
}

Następnie możesz mieć tę funkcję porównania:

compare_mtime() { [[ $1 -nt $2 ]]; }

I użyć:

$ qsort compare_mtime *
$ declare -p qsort_ret

aby pliki w bieżącym folderze były posortowane według czasu modyfikacji (od najnowszych).

UWAGA. Te funkcje to czysty Bash! żadnych zewnętrznych narzędzi i podpowłok! są one bezpieczne dla wszystkich zabawnych symboli, które możesz mieć (spacje, znaki nowej linii, znaki globu itp.).

Jeśli nie potrzebujesz obsługiwać specjalnych znaków powłoki w elementach tablicy:

array=(a c b f 3 5)
sorted=($(printf '%s\n' "${array[@]}"|sort))

W przypadku basha i tak będziesz potrzebować zewnętrznego programu do sortowania.

Z zsh nie są potrzebne żadne zewnętrzne programy, a specjalne znaki powłoki są łatwo obsługiwane:

% array=('a a' c b f 3 5); printf '%s\n' "${(o)array[@]}" 
3
5
a a
b
c
f

ksh musi set -ssortować ASCIIbetically .

tl; dr :

Sortuj tablicę a_ini przechowuj wynik w a_out(elementy nie mogą mieć osadzonych znaków nowej linii ^[1] ):

Bash v4 +:

readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

Bash v3:

IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)

Zalety w stosunku do rozwiązania Antak :

• Nie musisz martwić się przypadkowym globowaniem (przypadkową interpretacją elementów tablicy jako wzorców nazw plików), więc nie jest potrzebne żadne dodatkowe polecenie, aby wyłączyć globowanie ( set -fi set +fprzywrócić je później).

• Nie musisz się martwić o resetowanie za IFSpomocą unset IFS. ^[2]

Lektura opcjonalna: wyjaśnienie i przykładowy kod

Powyższe łączy kod Bash z zewnętrznym narzędziem sortdla rozwiązania, które działa z dowolnymi elementami jednowierszowymi i sortowaniem leksykalnym lub numerycznym (opcjonalnie według pola) :

• Wydajność : w przypadku około 20 lub więcej elementów będzie to szybsze niż zwykłe rozwiązanie Bash - znacznie i coraz częściej, gdy przekroczysz około 100 elementów.
  ^{(Dokładne progi będą zależeć od konkretnych danych wejściowych, maszyny i platformy).}

  • Powodem, dla którego jest szybki, jest to, że unika pętli Bash .

• printf '%s\n' "${a_in[@]}" | sort wykonuje sortowanie (domyślnie leksykalnie - patrz sortspecyfikacja POSIX ):

  • "${a_in[@]}"bezpiecznie interpretuje elementy tablicy a_injako pojedyncze argumenty , niezależnie od tego, co zawierają (w tym spacje).

  • printf '%s\n' następnie wypisuje każdy argument - tj. każdy element tablicy - w osobnym wierszu, tak jak jest.

• Zwróć uwagę na użycie substytucji procesu ( <(...)), aby zapewnić posortowane dane wyjściowe jako dane wejściowe do read/ readarray(przez przekierowanie do standardowego wejścia <), ponieważ read/ readarraymusi działać w bieżącej powłoce (nie może działać w podpowłoce ), aby zmienna wyjściowa a_outbyła widoczna do bieżącej powłoki (aby zmienna pozostała zdefiniowana w pozostałej części skryptu).

• Odczytywanie sortdanych wyjściowych do zmiennej tablicowej :

  • Bash v4 +: readarray -t a_outwczytuje poszczególne wiersze wyjściowe sortdo elementów zmiennej tablicowej a_out, bez uwzględniania końcowego \nw każdym elemencie ( -t).

  • Bash v3: readarraynie istnieje, więc readmusi być użyty:
    IFS=$'\n' read -d '' -r -a a_outmówi, readaby wczytać do -azmiennej array ( ) a_out, odczytać całe wejście, przez linie ( -d ''), ale podzielić je na elementy tablicy za pomocą znaków nowej linii ( IFS=$'\n'. $'\n', Co tworzy literalny znak nowej linii (LF ), jest tak zwanym ciągiem znaków ANSI w cudzysłowie C ).
    ( -ropcja, która praktycznie zawsze powinna być używana z read, wyłącza nieoczekiwaną obsługę \znaków.)

Przykładowy kod z adnotacjami:

#!/usr/bin/env bash

# Define input array `a_in`:
# Note the element with embedded whitespace ('a c')and the element that looks like
# a glob ('*'), chosen to demonstrate that elements with line-internal whitespace
# and glob-like contents are correctly preserved.
a_in=( 'a c' b f 5 '*' 10 )

# Sort and store output in array `a_out`
# Saving back into `a_in` is also an option.
IFS=$'\n' read -d '' -r -a a_out < <(printf '%s\n' "${a_in[@]}" | sort)
# Bash 4.x: use the simpler `readarray -t`:
# readarray -t a_out < <(printf '%s\n' "${a_in[@]}" | sort)

# Print sorted output array, line by line:
printf '%s\n' "${a_out[@]}"

Ze względu na użycie sortbez opcji daje to sortowanie leksykalne (cyfry sortują się przed literami, a sekwencje cyfr są traktowane leksykalnie, a nie jako liczby):

*
10
5
a c
b
f

Jeśli chcesz sortować liczbowo według pierwszego pola, użyjesz sort -k1,1nzamiast just sort, które daje (sortowanie nieliczbowe przed liczbami, a liczby sortowane poprawnie):

*
a c
b
f
5
10

^{[1] do elementów uchwytu z osadzonymi nowej linii, można użyć następującego wariantu (atakujących V4 +, jak GNU sort )
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z).
Pomocna odpowiedź Michała Górnego ma rozwiązanie Bash v3.}

^{[2] Podczas gdy IFS jest ustawiony w wariancie Bash v3, zmiana jest ograniczona do polecenia .
W przeciwieństwie do tego, co następuje IFS=$'\n' w odpowiedzi Antaka, jest raczej przypisaniem niż poleceniem, w którym to przypadku IFSzmiana jest globalna .}

Podczas 3-godzinnej podróży pociągiem z Monachium do Frankfurtu (do którego miałem kłopoty, bo jutro zaczyna się Oktoberfest) myślałem o swoim pierwszym poście. Wykorzystanie tablicy globalnej jest znacznie lepszym pomysłem na ogólną funkcję sortowania. Następująca funkcja obsługuje dowolne ciągi znaków (znaki nowej linii, spacje itp.):

declare BSORT=()
function bubble_sort()
{   #
    # @param [ARGUMENTS]...
    #
    # Sort all positional arguments and store them in global array BSORT.
    # Without arguments sort this array. Return the number of iterations made.
    #
    # Bubble sorting lets the heaviest element sink to the bottom.
    #
    (($# > 0)) && BSORT=("$@")
    local j=0 ubound=$((${#BSORT[*]} - 1))
    while ((ubound > 0))
    do
        local i=0
        while ((i < ubound))
        do
            if [ "${BSORT[$i]}" \> "${BSORT[$((i + 1))]}" ]
            then
                local t="${BSORT[$i]}"
                BSORT[$i]="${BSORT[$((i + 1))]}"
                BSORT[$((i + 1))]="$t"
            fi
            ((++i))
        done
        ((++j))
        ((--ubound))
    done
    echo $j
}

bubble_sort a c b 'z y' 3 5
echo ${BSORT[@]}

To drukuje:

3 5 a b c z y

Ten sam wynik jest tworzony z

BSORT=(a c b 'z y' 3 5) 
bubble_sort
echo ${BSORT[@]}

Zauważ, że prawdopodobnie Bash wewnętrznie używa inteligentnych wskaźników, więc operacja zamiany może być tania (chociaż wątpię). Jednak bubble_sortpokazuje, że bardziej zaawansowane funkcje, takie jak, merge_sortsą również w zasięgu języka powłoki.

Kolejne rozwiązanie wykorzystujące zewnętrzne sorti radzące sobie z dowolnymi znakami specjalnymi (z wyjątkiem NUL-ów :)). Powinien działać z bash-3.2 i GNU lub BSD sort(niestety POSIX nie zawiera -z).

local e new_array=()
while IFS= read -r -d '' e; do
    new_array+=( "${e}" )
done < <(printf "%s\0" "${array[@]}" | LC_ALL=C sort -z)

Najpierw spójrz na przekierowanie danych wejściowych na końcu. Używamy funkcji printfwbudowanej do zapisywania elementów tablicy, zakończonych zerem. Cytowanie zapewnia, że ​​elementy tablicy są przekazywane bez zmian, a specyfika powłoki printfpowoduje, że dla każdego pozostałego parametru ponownie wykorzystuje ostatnią część ciągu formatu. Oznacza to, że jest to odpowiednik czegoś takiego:

for e in "${array[@]}"; do
    printf "%s\0" "${e}"
done

Lista elementów zakończona znakiem null jest następnie przekazywana do sort. Ta -zopcja powoduje, że odczytuje elementy zakończone znakiem null, sortuje je i wyświetla również elementy zakończone znakiem null. Jeśli potrzebujesz tylko unikalnych elementów, możesz przejść, -uponieważ jest bardziej przenośny niż uniq -z. LC_ALL=CZapewnia stabilny porządek niezależnie od lokalizacji - czasami przydatne dla skryptów. Jeśli chcesz, sortaby szanował ustawienia regionalne, usuń to.

<()Konstrukcja uzyskuje deskryptor odczytu z wywoływanych rurociągu i <przekierowuje standardowe wejście whilepętli do niego. Jeśli potrzebujesz dostępu do standardowego wejścia wewnątrz potoku, możesz użyć innego deskryptora - ćwiczenie dla czytelnika :).

Wróćmy teraz do początku. readWbudowaną czyta wyjście z przekierowanych stdin. Ustawienie pustego IFSwyłącza dzielenie na słowa, które jest tu niepotrzebne - w rezultacie readczyta całą „linię” danych wejściowych do pojedynczej podanej zmiennej. -ropcja wyłącza przetwarzanie ucieczki, które jest tutaj niepożądane. Na koniec -d ''ustawia ogranicznik linii na NUL - to znaczy mówi, readaby czytać ciągi zakończone zerami.

W rezultacie pętla jest wykonywana raz dla każdego kolejnego elementu tablicy zakończonego zerem, a wartość jest przechowywana w e. Przykład po prostu umieszcza elementy w innej tablicy, ale możesz chcieć przetworzyć je bezpośrednio :).

Oczywiście to tylko jeden z wielu sposobów osiągnięcia tego samego celu. Jak widzę, jest to prostsze niż implementacja pełnego algorytmu sortowania w bashu, aw niektórych przypadkach będzie szybsze. Obsługuje wszystkie znaki specjalne, w tym znaki nowej linii i powinien działać na większości popularnych systemów. Co najważniejsze, może nauczyć Cię czegoś nowego i niesamowitego o bashu :).

Spróbuj tego:

echo ${array[@]} | awk 'BEGIN{RS=" ";} {print $1}' | sort

Wynik będzie:

3
5
za
b
do
fa

Problem rozwiązany.

Jeśli możesz obliczyć unikalną liczbę całkowitą dla każdego elementu tablicy, na przykład:

tab='0123456789abcdefghijklmnopqrstuvwxyz'

# build the reversed ordinal map
for ((i = 0; i < ${#tab}; i++)); do
    declare -g ord_${tab:i:1}=$i
done

function sexy_int() {
    local sum=0
    local i ch ref
    for ((i = 0; i < ${#1}; i++)); do
        ch="${1:i:1}"
        ref="ord_$ch"
        (( sum += ${!ref} ))
    done
    return $sum
}

sexy_int hello
echo "hello -> $?"
sexy_int world
echo "world -> $?"

wtedy możesz użyć tych liczb całkowitych jako indeksów tablic, ponieważ Bash zawsze używa rzadkich tablic, więc nie musisz się martwić o nieużywane indeksy:

array=(a c b f 3 5)
for el in "${array[@]}"; do
    sexy_int "$el"
    sorted[$?]="$el"
done

echo "${sorted[@]}"

• Plusy Szybki.
• Cons. Zduplikowane elementy są scalane i odwzorowanie zawartości na 32-bitowe unikalne liczby całkowite może być niemożliwe.

min sort:

#!/bin/bash
array=(.....)
index_of_element1=0

while (( ${index_of_element1} < ${#array[@]} )); do

    element_1="${array[${index_of_element1}]}"

    index_of_element2=$((index_of_element1 + 1))
    index_of_min=${index_of_element1}

    min_element="${element_1}"

        for element_2 in "${array[@]:$((index_of_element1 + 1))}"; do
            min_element="`printf "%s\n%s" "${min_element}" "${element_2}" | sort | head -n+1`"      
            if [[ "${min_element}" == "${element_2}" ]]; then
                index_of_min=${index_of_element2}
            fi
            let index_of_element2++
        done

        array[${index_of_element1}]="${min_element}"
        array[${index_of_min}]="${element_1}"

    let index_of_element1++
done

array=(a c b f 3 5)
new_array=($(echo "${array[@]}" | sed 's/ /\n/g' | sort))    
echo ${new_array[@]}

echo nowej tablicy będzie wyglądało następująco:

3 5 a b c f

Istnieje obejście zwykłego problemu ze spacjami i znakami nowej linii:

Użyj znak, który nie jest w oryginalnej tablicy (jak $'\1'lub $'\4'lub podobny).

Ta funkcja wykonuje zadanie:

# Sort an Array may have spaces or newlines with a workaround (wa=$'\4')
sortarray(){ local wa=$'\4' IFS=''
             if [[ $* =~ [$wa] ]]; then
                 echo "$0: error: array contains the workaround char" >&2
                 exit 1
             fi

             set -f; local IFS=$'\n' x nl=$'\n'
             set -- $(printf '%s\n' "${@//$nl/$wa}" | sort -n)
             for    x
             do     sorted+=("${x//$wa/$nl}")
             done
       }

To posortuje tablicę:

$ array=( a b 'c d' $'e\nf' $'g\1h')
$ sortarray "${array[@]}"
$ printf '<%s>\n' "${sorted[@]}"
<a>
<b>
<c d>
<e
f>
<gh>

Spowoduje to narzekanie, że tablica źródłowa zawiera znak obejścia:

$ array=( a b 'c d' $'e\nf' $'g\4h')
$ sortarray "${array[@]}"
./script: error: array contains the workaround char

opis

• Ustawiliśmy dwie zmienne lokalne wa(znak obejścia) i pusty IFS
• Następnie (z wartością ifs null) sprawdzamy, czy cała tablica $*.
• Nie zawiera zwęglenia [[ $* =~ [$wa] ]].
• Jeśli tak, wyświetl komunikat i zasygnalizuj błąd: exit 1
• Unikaj rozszerzeń nazw plików: set -f
• Ustaw nową wartość IFS ( IFS=$'\n') jako zmienną pętlową xi nową linię var ( nl=$'\n').
• Drukujemy wszystkie wartości otrzymanych argumentów (tablica wejściowa $@).
• ale każdy nowy wiersz zastępujemy znakiem obejścia "${@//$nl/$wa}".
• wyślij te wartości do posortowania sort -n.
• i umieść z powrotem wszystkie posortowane wartości w argumentach pozycyjnych set --.
• Następnie przypisujemy każdy argument po kolei (aby zachować znaki nowej linii).
• w pętli for x
• do nowej tablicy: sorted+=(…)
• wewnątrz cudzysłowów, aby zachować istniejącą nową linię.
• przywracanie obejścia do nowego wiersza "${x//$wa/$nl}".
• Gotowe

To pytanie jest ściśle powiązane. A tak przy okazji, oto połączenie w Bash (bez procesów zewnętrznych):

mergesort() {
  local -n -r input_reference="$1"
  local -n output_reference="$2"
  local -r -i size="${#input_reference[@]}"
  local merge previous
  local -a -i runs indices
  local -i index previous_idx 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_idx=indices[$((index + 1))]
      run_a_stop=runs[previous_idx]
      run_b_idx=runs[previous_idx]
      run_b_stop=runs[indices[$((index + 2))]]
      unset runs[previous_idx]
      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
}

declare -ar input=({z..a}{z..a})
declare -a output

mergesort input output

echo "${input[@]}"
echo "${output[@]}"

Nie jestem przekonany, że będziesz potrzebować zewnętrznego programu do sortowania w Bash.

Oto moja implementacja prostego algorytmu sortowania bąbelkowego.

function bubble_sort()
{   #
    # Sorts all positional arguments and echoes them back.
    #
    # Bubble sorting lets the heaviest (longest) element sink to the bottom.
    #
    local array=($@) max=$(($# - 1))
    while ((max > 0))
    do
        local i=0
        while ((i < max))
        do
            if [ ${array[$i]} \> ${array[$((i + 1))]} ]
            then
                local t=${array[$i]}
                array[$i]=${array[$((i + 1))]}
                array[$((i + 1))]=$t
            fi
            ((i += 1))
        done
        ((max -= 1))
    done
    echo ${array[@]}
}

array=(a c b f 3 5)
echo " input: ${array[@]}"
echo "output: $(bubble_sort ${array[@]})"

To powinno wydrukować:

 input: a c b f 3 5
output: 3 5 a b c f

a=(e b 'c d')
shuf -e "${a[@]}" | sort >/tmp/f
mapfile -t g </tmp/f

sorted=($(echo ${array[@]} | tr " " "\n" | sort))

W duchu bash / linux, dla każdego kroku chciałbym potokować najlepsze narzędzie wiersza poleceń. sortwykonuje główną pracę, ale potrzebuje danych wejściowych oddzielonych znakiem nowej linii zamiast spacji, więc bardzo prosty potok powyżej po prostu wykonuje:

Zawartość tablicy echa -> zastąp spację nową linią -> sortuj

$() jest powtórzenie wyniku

($()) polega na umieszczeniu w tablicy „wyniku wyświetlonego echo”

Uwaga : jak wspomniał @sorontar w komentarzu do innego pytania:

Część posortowana = ($ (...)) używa operatora „split and glob”. Powinieneś wyłączyć glob: set -f lub set -o noglob lub shopt -op noglob lub element tablicy, taki jak *, zostanie rozszerzony do listy plików.