How to sort an array in Bash

Question

I have an array in Bash, for example:

array=(a c b f 3 5)

I need to sort the array. Not just displaying the content in a sorted way, but to get a new array with the sorted elements. The new sorted array can be a completely new one or the old one.

Solution 1

You don't really need all that much code:

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

Supports whitespace in elements (as long as it's not a newline), and works in Bash 3.x.

e.g.:

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

Note: @sorontar has pointed out that care is required if elements contain wildcards such as * or ?:

The sorted=($(...)) part is using the "split and glob" operator. You should turn glob off: set -f or set -o noglob or shopt -op noglob or an element of the array like * will be expanded to a list of files.

What's happening:

The result is a culmination six things that happen in this order:

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

First, the IFS=$'\n'

This is an important part of our operation that affects the outcome of 2 and 5 in the following way:

Given:

• "${array[*]}" expands to every element delimited by the first character of IFS
• sorted=() creates elements by splitting on every character of IFS

IFS=$'\n' sets things up so that elements are expanded using a new line as the delimiter, and then later created in a way that each line becomes an element. (i.e. Splitting on a new line.)

Delimiting by a new line is important because that's how sort operates (sorting per line). Splitting by only a new line is not-as-important, but is needed preserve elements that contain spaces or tabs.

The default value of IFS is a space, a tab, followed by a new line, and would be unfit for our operation.

Next, the sort <<<"${array[*]}" part

<<<, called here strings, takes the expansion of "${array[*]}", as explained above, and feeds it into the standard input of sort.

With our example, sort is fed this following string:

a c
b
f
3 5

Since sort sorts, it produces:

3 5
a c
b
f

Next, the sorted=($(...)) part

The $(...) part, called command substitution, causes its content (sort <<<"${array[*]}) to run as a normal command, while taking the resulting standard output as the literal that goes where ever $(...) was.

In our example, this produces something similar to simply writing:

sorted=(3 5
a c
b
f
)

sorted then becomes an array that's created by splitting this literal on every new line.

Finally, the unset IFS

This resets the value of IFS to the default value, and is just good practice.

It's to ensure we don't cause trouble with anything that relies on IFS later in our script. (Otherwise we'd need to remember that we've switched things around--something that might be impractical for complex scripts.)

Solution 2

Original response:

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

output:

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

Note this version copes with values that contains special characters or whitespace (except newlines)

Note readarray is supported in bash 4+.

---

Edit Based on the suggestion by @Dimitre I had updated it to:

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

which has the benefit of even understanding sorting elements with newline characters embedded correctly. Unfortunately, as correctly signaled by @ruakh this didn't mean the the result of readarray would be correct, because readarray has no option to use NUL instead of regular newlines as line-separators.

Solution 3

Here's a pure Bash quicksort implementation:

#!/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
      # This sorts strings lexicographically.
      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[@]}" )
}

Use as, e.g.,

$ 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")'

This implementation is recursive… so here's an iterative quicksort:

#!/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
}

In both cases, you can change the order you use: I used string comparisons, but you can use arithmetic comparisons, compare wrt file modification time, etc. just use the appropriate test; you can even make it more generic and have it use a first argument that is the test function use, e.g.,

#!/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
}

Then you can have this comparison function:

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

and use:

$ qsort compare_mtime *
$ declare -p qsort_ret

to have the files in current folder sorted by modification time (newest first).

NOTE. These functions are pure Bash! no external utilities, and no subshells! they are safe wrt any funny symbols you may have (spaces, newline characters, glob characters, etc.).

NOTE2. The test [[ $i < $pivot ]] is correct. It uses the lexicographical string comparison. If your array only contains integers and you want to sort numerically, use ((i < pivot)) instead. _{Please don't edit this answer to change that. It has already been edited (and rolled back) a couple of times. The test I gave here is correct and corresponds to the output given in the example: the example uses both strings and numbers, and the purpose is to sort it in lexicographical order. Using ((i < pivot)) in this case is wrong.}

Solution 4

If you don't need to handle special shell characters in the array elements:

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

With bash you'll need an external sorting program anyway.

With zsh no external programs are needed and special shell characters are easily handled:

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

ksh has set -s to sort ASCIIbetically.

Solution 5

tl;dr:

Sort array a_in and store the result in a_out (elements must not have embedded newlines^[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)

Advantages over antak's solution:

• You needn't worry about accidental globbing (accidental interpretation of the array elements as filename patterns), so no extra command is needed to disable globbing (set -f, and set +f to restore it later).

• You needn't worry about resetting IFS with unset IFS.^[2]

---

Optional reading: explanation and sample code

The above combines Bash code with external utility sort for a solution that works with arbitrary single-line elements and either lexical or numerical sorting (optionally by field):

• Performance: For around 20 elements or more, this will be faster than a pure Bash solution - significantly and increasingly so once you get beyond around 100 elements.
  ^{(The exact thresholds will depend on your specific input, machine, and platform.)}

  • The reason it is fast is that it avoids Bash loops.

• printf '%s\n' "${a_in[@]}" | sort performs the sorting (lexically, by default - see sort's POSIX spec):

  • "${a_in[@]}" safely expands to the elements of array a_in as individual arguments, whatever they contain (including whitespace).

  • printf '%s\n' then prints each argument - i.e., each array element - on its own line, as-is.

• Note the use of a process substitution (<(...)) to provide the sorted output as input to read / readarray (via redirection to stdin, <), because read / readarray must run in the current shell (must not run in a subshell) in order for output variable a_out to be visible to the current shell (for the variable to remain defined in the remainder of the script).

• Reading sort's output into an array variable:

  • Bash v4+: readarray -t a_out reads the individual lines output by sort into the elements of array variable a_out, without including the trailing \n in each element (-t).

  • Bash v3: readarray doesn't exist, so read must be used:
    IFS=$'\n' read -d '' -r -a a_out tells read to read into array (-a) variable a_out, reading the entire input, across lines (-d ''), but splitting it into array elements by newlines (IFS=$'\n'. $'\n', which produces a literal newline (LF), is a so-called ANSI C-quoted string).
    (-r, an option that should virtually always be used with read, disables unexpected handling of \ characters.)

Annotated sample code:

#!/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[@]}"

Due to use of sort without options, this yields lexical sorting (digits sort before letters, and digit sequences are treated lexically, not as numbers):

*
10
5
a c
b
f

If you wanted numerical sorting by the 1st field, you'd use sort -k1,1n instead of just sort, which yields (non-numbers sort before numbers, and numbers sort correctly):

*
a c
b
f
5
10

---

^{[1] To handle elements with embedded newlines, use the following variant (Bash v4+, with GNU sort):
readarray -d '' -t a_out < <(printf '%s\0' "${a_in[@]}" | sort -z).
Michał Górny's helpful answer has a Bash v3 solution.}

^{[2] While IFS is set in the Bash v3 variant, the change is scoped to the command.
By contrast, what follows IFS=$'\n'  in antak's answer is an assignment rather than a command, in which case the IFS change is global.}

View more solutions

Comments

[Dimitre Radoulov]

Nice, it should be also noted that readarray is available since version 4 of bash. It could be shortened a bit: readarray -t sorted < <(printf '%s\n' "${array[@]}" | sort)

[sehe]

@Dimitre: I took your suggestion and fixed the whitespace handling to work with anything (using nullchar-delimiters internally). Cheers

[Dimitre Radoulov]

Yes the sort -z is a useful improvement, I suppose the -z option is a GNU sort extention.

[sehe]

Very nice background info. I would almost ask for a demo on how ksh would use the set -s flag... but then again, the question is on bash, so that would be rather off-topic

[Dimitre Radoulov]

This should work with most KornShell implementations (for example ksh88 and pdksh): set -A array x 'a a' d; set -s -- "${array[@]}"; set -A sorted "$@" And, of course, the set command will reset the current positional parameters, if any.

[sehe]

You are a veritable fountain of shell knowledge. I'm sure you must have photographics memory or something, because this kind of subtle differences elude most of the other members of the human species :), +1 for the complete package of info

[ruakh]

I don't know if I agree that that "understand[s] elements with newline characters embedded". If the filename is $'z\na', then it will successfully keep the z and a together during sorting, but they'll still end up in separate array-elements, with the $'\n' being swallowed. It's unfortunate that there's no way to tell readarray to use $'\0' instead of $'\n'.

[sehe]

@ruakh: Very good spot. Fixed the answer, thanks for the heads up

[Bob Bell]

If you want to handle embedded newlines, you can roll your own readarray. For example: sorted=(); while read -d $'\0' elem; do sorted[${#sorted[@]}]=$elem; done < <(printf '%s\0' "${array[@]}" | sort -z). This also works in you are using bash v3 instead of bash v4, because readarray isn't available in bash v3.

[Peter Oram]

Should edit this to put the output into a new array to fully answer his question.

[Robottinosino]

Bubble sort? Wow.. Obama says "bubble sort would be the wrong way to go" -> youtube.com/watch?v=k4RRi_ntQc8

[Andreas Spindler]

Well, it seems while the O-guy wanted to be smart he hadn't sensed that this is not a 50/50 chance question. A predecessor in the position of O-guy, let's tell him the B-guy, once did much better (Reynoldsburg, Ohio, Oct 2000): "I think if you know what you believe, it makes it a lot easier to answer questions. I can't answer your question." So this B-guy really knows something about Boolean logic. The O-guy doesn't.

[user1527227]

Can someone please explain why there are two < < ? Why isn't it just: readarray -t sorted < (printf '%s\0' "${array[@]}" | sort -z | xargs -0n1). Thank you.

[sehe]

@user1527227 It's input redirection (<) combined with process substitution <(...). Or to put it intuitively: because (printf "bla") is not a file.

[xor]

very nice. Why the IFS tho? I dont think this is necessary

[antak]

@xxor without the IFS, it'll split your elements into little pieces if they have whitespaces in them. Try the e.g. with IFS=$'\n' omitted and see!

[xor]

ahh, good solution indeed. I only tried on my own sort without whitespaces in it. now i see

[user32004]

Very nice. Could you explain for the average bash user how this solution works?

[mklement0]

Kudos for impressive Bashing that offers great flexibility with respect to input elements and sort criteria. If line-based sorting with the sort options that sort offers is sufficient, a sort + read -a solution will be faster starting at around, say, 20 items, and increasingly and significantly faster the more elements you're dealing with. E.g., on my late-2012 iMac running OSX 10.11.1 with a Fusion Drive: 100-element array: ca. 0.03s secs. (qsort()) vs. ca. 0.005 secs. (sort + read -a); 1000-element array: ca. 0.375 secs. (qsort()) vs. ca. 0.014 secs (sort + read -a).

[Dirk Herrmann]

Great solution and very helpful explanation, thanks. One extension: Without setting IFS to empty, leading whitespace will also be eliminated - even if otherwise no word splitting was done.

[lmat - Reinstate Monica]

Now, with the IFS, it splits your elements into little pieces if they have only one particular kind of whitespace in it. Good; not perfect :-)

[gniourf_gniourf]

In the spirit of bash / linux: I guess you didn't understand the spirit at all. Your code is completely broken (pathname expansion and word splitting). This would be better (Bash≥4): mapfile -t sorted < <(printf '%s\n' "${array[@]}" | sort), otherwise sorted=(); while IFS= read -r line; do sorted+=( "$line" ); done < <(printf '%s\n' | sort).

[gniourf_gniourf]

The antipatterns you're using are: echo ${array[@]} | tr " " "\n": this will break if the fields of array contain whitespaces and glob characters. Besides, it spawns a subshell and uses a useless external command. And due to echo being dumb, it will break if your array starts with -e, -E or -n. Instead use: printf '%s\n' "${array[@]}". The other antipattern is : ($()) is to put the "echoed result" in an array. Certainly not! this is a horrible antipattern that breaks because of pathname expansion (globbing) and word splitting. Never use this horror.

[jww]

Bubble sort is O(n^2). I seem to recall most sorting algorithms use an O(n lg(n)) until the final dozen elements or so. For the final elements, selection sort is used.

[Mark H]

Is unset IFS necessary? I thought prepending IFS= to a command scoped the change to that command only, returning to its previous value automatically afterwards.

[antak]

@MarkH It's necessary because sorted=() is not a command but rather a second variable assignment.

[done]

New on bash 4.4 readarray could use null delimiter with -d ''.

[sehe]

@sorontar I can't find any documentation to suggest that -d '' would use the NUL character as delimiter. Did you find that anywhere?

[done]

Start a bash 4.4 and write help readarray (mapfile) to find that it accepts a -d option to select the delimiter. Otherwise, read here; "mapfile" new option "-d" 4.4-alpha. Also at the end of this answer.

[done]

And this is even more specific BASH’s ‘read’ built-in supports '\0' as delimiter.

[sehe]

@sorontar Thanks for those links. I've tried things, but apparently I'm doing something wrong, or it's not quite working as expected/required for this answer i.imgur.com/sMEOWwk.png - Am I missing something?

[done]

Please try: readarray -d '' -t arr < <(printf 'a\0b\0c\0def\0'); printf '%s\n' "${arr[@]}".

[sehe]

@sorontar COOL. It's abusing the NUL-terminator for that empty string ''. Clever. Sounds a bit brittle, but definitely clever, and if even Gentoo ebuilds are relying on the behaviour, let's assume it will be kept :)

[michael]

The top answer has the "horrible antipattern". And way to go to downvote someone else's answer to the question you answered yourself.

[Charles Duffy]

I'd suggest adding that to the sample code, rather than as an English-language comment someone may or may not read or adopt for their own implementation. (Actually didn't see that provisio in the answer at all, and almost duplicated sorontar's comment before seeing it had already been made).

[Charles Duffy]

BTW, if we're on a GNU system (or somewhere else with sort -z), it'd be safer to NUL-delimit the entries -- that way we're not splitting entries with newline literals into multiple entries in the newly created array. out=( ); while IFS= read -r -d '' entry; do out+=( "$entry" ); done < <(printf '%s\0' "${array[@]}" | sort -z)

[jarno]

I wonder why "${array[@]}" does not work as here string? It is supposed to handle spaces in elements better than "${array[*]}" like it does in your example in the printf command. array=("a c" b f "3 5"); IFS=$'\n' printf '[%s]\n' "${array[*]}"; unset -v IFS does not work, even when IFS is set.

[mklement0]

@jarno: It's explained in the answer, but just to summarize it: "${array[*]}" expands to a single string formed by joining the array elements with the 1st char. of $IFS. By contrast, "${array[@]}" expands to multiple arguments, which, when used in a string context, are always joined with a space, irrespective of the value of $IFS.

[WinEunuuchs2Unix]

Nice. I remember quick sort from college days but will also research bubble sort. For my sorting needs I have first and second elements forming key followed by one data element (which I may expand later). Your code could be improved with number of key elements (parm1) and number of data elements (parm2). For OP the parameters would be 1 and 0. For me the parameters would be 2 and 1. In any respect your answer has most promise.

[Eli Barzilay]

Cute answer, but you're already showing printfs use, which can be used for an easier solution that doesn't depend on IFS for generating output: IFS=$'\n' sorted=($(printf '%s\n' "${array[@]}" | sort)).

[johnraff]

The function could be made more easily portable by making BSORT a local array with a nameref to whatever array is to be sorted. ie local -n BSORT="$1" at the start of the function. Then you can run bubble_sort myarray to sort myarray.

[antak]

@EliBarzilay I don't get what's easier. What you wrote is longer than what's in the answer and sets IFS anyhow.

[Eli Barzilay]

@antak, Sorry, I think that I actually meant to say that it doesn't depend on <<<"..." and how that interacts with IFS.

[user1404316]

Instead of performing an unset IFS, first at the beginning save IFS into something like OLD_IFS, and then at the end restore IFS to the original value.

[antak]

@user1404316 I think you should explain why that's useful. Maybe if you're writing a script that reads IFS? Though the question then is why.. Or maybe it's for modularity within the script? In which case IFS=$OLD_IFS wouldn't restore the old value if it was previously unset, but instead sets it to blank which can do more damage than good... I think a script implicitly has a certain level of interdependency, so we design and make rules on how our scripts should behave. To this end, using OLD_IFS seems no more beneficial than just sticking with unset IFS.

[Page2PagePro]

With a dataset of uncast string integers I found if [ "$i" -lt "$pivot" ]; then was required otherwise the resolved "2" < "10" returned true. I believe this to be POSIX vs. Lexicographical; or perhaps Inline Link.

[Robin A. Meade]

Instead of introducing local variable e and setting empty IFS, use the REPLY variable.

[haridsv]

Why not set IFS inside the subshell so that it doesn't need to unset or saved and restored? sorted=($(IFS=$'\n' ; sort <<<"${array[*]}"))

[antak]

@haridsv Good observation. However, our IFS is also required by the sorted=(...) operation, which is outside the subshell.

[haridsv]

@antak I don't think so, at least not for the sake of sorted array.

[antak]

@haridsv For example, if you run the example starting array=("a c" b f "3 5") but move IFS= inside the subshell, the elements a c and 3 5 will be broken up into four elements a, c, 3 and 5.

[haridsv]

@antak I see what you are saying, thanks for pointing it out!

[peterRepeater]

Do you even need to mess with IFS? sort has a field separator built-in: sort --field-separator=' ' <<<"${array[*]}"

[antak]

@peterRepeater See this comment, because the same thing will happen with your idea. You should try it by changing the example I posted and see.

[HelloIT]

This algorithm doesn't work at all times. If you give as input numbers "21 1 4 2 18" it sorts them using the 1st digit only and not all digits. Hence the result is "1 18 2 21 4"

[sehe]

@HelloIT so it works. It just doesn't sort numbers. That's expected and by design. Luckily, you can just clue sort in: sort -n

[mr.spuratic]

Interesting technique, I've used a variant for finding max/min values without explicit compare/sort. But, un-weighted addition without regard to length won't work: "z" sorts before "aaaa", so you can't use this for words as you show above.

[Kyle Rose]

Wouldn't { local IFS=$'\n'; sorted=($(sort <<<"${array[*]}")); } be better because it doesn't presume anything about the prior value of IFS?

[antak]

@KyleRose That gives me local: can only be used in a function in my bash 4.

[Kyle Rose]

@antak Huh. I don't get an error, probably because I only tried it within a function, in which case it isn't actually doing what I think. Thanks.

[Kyle Rose]

In this case, I would fall back to the OLDIFS=$IFS ... IFS=$OLDIFS pattern.

[Christopher King]

Great discussion of the pitfalls!

[von spotz]

Upvote for great description whats happening

[KamilCuk]

Have you tested the code? It does not work. $ref is local to the subshell that runs mapfile, it can't affect parent shell. Could be, that you tested the code under zsh or fish - the question is about bash.