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

User · Accepted Answer

You don t really need all that much code   IFS    n  sorted    sort  lt  lt  lt    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  lt  lt  lt    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    IFS    n     array       lt  lt  lt  sort sorted          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  lt  lt  lt    array      part   lt  lt  lt   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  lt  lt  lt    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

User · Answer

sorted    echo   array       tr       n    sort    In the spirit of bash   linux  I would pipe the best command-line tool for each step  sort does the main job but needs input separated by newline instead of space  so the very simple pipeline above simply does   Echo array content --  replace space by newline --  sort      is to echo the result        is to put the  echoed result  in an array  Note  as  sorontar mentioned in a comment to a different question      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

User · Answer

I am not convinced that you ll need an external sorting program in Bash   Here is my implementation for the simple bubble-sort algorithm   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  gt  0       do         local i 0         while   i  lt  max           do             if     array  i     gt    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         This shall print    input  a c b f 3 5 output  3 5 a b c f

User · Answer

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  lt   lt  printf   s n     a in        sort    Bash v3   IFS    n  read -d    -r -a a out  lt   lt  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   lt        to provide the sorted output as input to read   readarray  via redirection to stdin   lt    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  lt   lt  printf   s n     a in        sort    Bash 4 x  use the simpler  readarray -t     readarray -t a out  lt   lt  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  lt   lt  printf   s 0     a in        sort -z   Michal 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

User · Answer

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

User · Answer

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    amp  amp  return 0    pivot  1    shift    for i  do         This sorts strings lexicographically        if     i  lt   pivot     then          smaller     quot  i quot          else          larger     quot  i quot          fi    done    qsort  quot   smaller     quot     smaller    quot   qsort ret     quot       qsort  quot   larger     quot     larger    quot   qsort ret     quot       qsort ret    quot   smaller     quot   quot  pivot quot   quot   larger     quot       Use as  e g     array  a c b f 3 5    qsort  quot   array     quot    declare -p qsort ret declare -a qsort ret    0   quot 3 quot   1   quot 5 quot   2   quot a quot   3   quot b quot   4   quot c quot   5   quot f quot     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    amp  amp  return 0    local stack   0      -1     beg end i pivot smaller larger    qsort ret   quot    quot      while      stack        do       beg   stack 0         end   stack 1         stack    quot   stack    2  quot          smaller    larger          pivot   qsort ret beg         for   i beg 1 i lt  end   i    do          if     quot   qsort ret i   quot   lt   quot  pivot quot      then             smaller     quot   qsort ret i   quot             else             larger     quot   qsort ret i   quot             fi       done       qsort ret    quot   qsort ret    0 beg  quot   quot   smaller     quot   quot  pivot quot   quot   larger     quot   quot   qsort ret    end 1  quot          if      smaller     gt  2    then stack     quot  beg quot   quot    beg    smaller    -1   quot     fi       if      larger     gt  2    then stack     quot    end-   larger     1   quot   quot  end quot     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             lt  1    amp  amp  return 0    local compare fun  1    shift    local stack   0      -1     beg end i pivot smaller larger    qsort ret   quot    quot      while      stack        do       beg   stack 0         end   stack 1         stack    quot   stack    2  quot          smaller    larger          pivot   qsort ret beg         for   i beg 1 i lt  end   i    do          if  quot  compare fun quot   quot   qsort ret i   quot   quot  pivot quot   then             smaller     quot   qsort ret i   quot             else             larger     quot   qsort ret i   quot             fi       done       qsort ret    quot   qsort ret    0 beg  quot   quot   smaller     quot   quot  pivot quot   quot   larger     quot   quot   qsort ret    end 1  quot          if      smaller     gt  2    then stack     quot  beg quot   quot    beg    smaller    -1   quot     fi       if      larger     gt  2    then stack     quot    end-   larger     1   quot   quot  end quot     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  lt   pivot    is correct  It uses the lexicographical string comparison  If your array only contains integers and you want to sort numerically  use   i  lt  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  lt  pivot   in this case is wrong

User · Answer

try this   echo   array       awk  BEGIN RS        print  1     sort   Output will be    3 5 a b c f   Problem solved

User · Answer

min sort        bin bash array         index of element1 0  while      index of element1   lt     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

User · Answer

Original response   array  a c b  f f  3 5  readarray -t sorted  lt   lt  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  lt   lt  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

User · Answer

If you can compute a unique integer for each element in the array  like this   tab  0123456789abcdefghijklmnopqrstuvwxyz     build the reversed ordinal map for   i   0  i  lt     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  lt     1   i      do         ch    1 i 1           ref  ord  ch             sum       ref         done     return  sum    sexy int hello echo  hello - gt      sexy int world echo  world - gt        then  you can use these integers as array indexes  because Bash always use sparse array  so no need to worry about unused indexes   array  a c b f 3 5  for el in    array       do     sexy int   el      sorted       el  done  echo    sorted         Pros  Fast  Cons  Duplicated elements are merged  and it can be impossible to map contents to 32-bit unique integers

User · Answer

a  e b  c d   shuf -e    a        sort  gt  tmp f mapfile -t g  lt  tmp f

User · Answer

There is a workaround for the usual problem of spaces and newlines     Use a character that is not in the original array  like    1  or    4  or similar    This function gets the job done     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   gt  amp 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            This will sort the array     array   a b  c d    e nf    g 1h     sortarray    array        printf   lt  s gt  n     sorted       lt a gt   lt b gt   lt c d gt   lt e f gt   lt gh gt    This will complain that the source array contains the workaround character     array   a b  c d    e nf    g 4h     sortarray    array        script  error  array contains the workaround char   description   We set two local variables wa  workaround char  and a null IFS Then  with ifs null  we test that the whole array     Does not contain any woraround char            wa      If it does  raise a message and signal an error  exit 1 Avoid filename expansions  set -f Set a new value of IFS  IFS    n   a loop variable x and a newline var  nl    n    We print all values of the arguments received  the input array      but we replace any new line by the workaround char        nl  wa    send those values to be sorted sort -n  and place back all the sorted values in the positional arguments set --  Then we assign each argument one by one  to preserve newlines   in a loop for x to a new array  sorted        inside quotes to preserve any existing newline  restoring the workaround to a newline    x   wa  nl    done

User · Answer

array  z  b c      set  quot   array     quot   printf   s n   quot    quot             sort         mapfile -t array  declare -p array declare -a array   0   quot b c quot   1   quot z quot     Open an inline function       to get a fresh set of positional arguments  e g   1   2  etc   Copy the array to the positional arguments   e g  set  quot   array     quot  will copy the nth array argument to the nth positional argument  Note the quotes preserve whitespace that may be contained in an array element   Print each positional argument  e g  printf   s n   quot    quot  will print each positional argument on its own line   Again  note the quotes preserve whitespace that may be contained in each positional argument   Then sort does its thing  Read the stream into an array with mapfile  e g  mapfile -t array reads each line into the variable array and the -t ignores the  n in each line   Dump the array to show its been sorted   As a function  set  m shopt -s lastpipe  sort array          declare -n ref  1     set  quot   ref     quot      printf   s n   quot    quot        sort         mapfile -t  ref    then array  z y x   sort array array  declare -p array declare -a array   0   quot x quot   1   quot y quot   2   quot z quot    I look forward to being ripped apart by all the UNIX gurus

User · Answer

This question looks closely related  And BTW  here s a mergesort in Bash  without external processes    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  gt   size    then break 2  fi       if       output reference index     lt    previous      then break  fi       previous    output reference index        done     previous    output reference index        runs   index    done   runs   size     while       runs       gt  2    do     indices      runs           merge     output reference           for   index   0  index  lt      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  lt  run a stop  amp  amp  run b idx  lt  run b stop    do         if       merge run a idx     lt     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  lt  run a stop    do         output reference merged idx       merge run a idx            done       while   run b idx  lt  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

User · Answer

Another solution that uses external sort and copes with any special characters  except for NULs      Should work with bash-3 2 and GNU or BSD sort  sadly  POSIX doesn t include -z    local e new array    while IFS  read -r -d    e  do     new array       e     done  lt   lt  printf   s 0     array        LC ALL C sort -z    First look at the input redirection at the end  We re using printf built-in to write out the array elements  zero-terminated  The quoting makes sure array elements are passed as-is  and specifics of shell printf cause it to reuse the last part of format string for each remaining parameter  That is  it s equivalent to something like   for e in    array       do     printf   s 0     e   done   The null-terminated element list is then passed to sort  The -z option causes it to read null-terminated elements  sort them and output null-terminated as well  If you needed to get only the unique elements  you can pass -u since it is more portable than uniq -z  The LC ALL C ensures stable sort order independently of locale     sometimes useful for scripts  If you want the sort to respect locale  remove that   The  lt    construct obtains the descriptor to read from the spawned pipeline  and  lt  redirects the standard input of the while loop to it  If you need to access the standard input inside the pipe  you may use another descriptor     exercise for the reader      Now  back to the beginning  The read built-in reads output from the redirected stdin  Setting empty IFS disables word splitting which is unnecessary here     as a result  read reads the whole  line  of input to the single provided variable  -r option disables escape processing that is undesired here as well  Finally  -d    sets the line delimiter to NUL     that is  tells read to read zero-terminated strings   As a result  the loop is executed once for every successive zero-terminated array element  with the value being stored in e  The example just puts the items in another array but you may prefer to process them directly      Of course  that s just one of the many ways of achieving the same goal  As I see it  it is simpler than implementing complete sorting algorithm in bash and in some cases it will be faster  It handles all special characters including newlines and should work on most of the common systems  Most importantly  it may teach you something new and awesome about bash

User · Answer

array  a c b f 3 5  new array    echo    array        sed  s    n g    sort       echo   new array       echo contents of new array will be   3 5 a b c f

User · Answer

In the 3-hour train trip from Munich to Frankfurt  which I had trouble to reach because Oktoberfest starts tomorrow  I was thinking about my first post  Employing a global array is a much better idea for a general sort function  The following function handles arbitary strings  newlines  blanks etc     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                  gt  0    amp  amp  BSORT            local j 0 ubound       BSORT     - 1       while   ubound  gt  0       do         local i 0         while   i  lt  ubound           do             if      BSORT  i      gt     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       This prints   3 5 a b c z y   The same output is created from  BSORT  a c b  z y  3 5   bubble sort echo   BSORT       Note that probably Bash internally uses smart-pointers  so the swap-operation could be cheap  although I doubt it   However  bubble sort demonstrates that more advanced functions like merge sort are also in the reach of the shell language

[arrays] How to sort an array in Bash

What's happening:

First, the `IFS=$'\n'`

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

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

Finally, the `unset IFS`

Examples related to arrays

Examples related to bash

Examples related to shell

Examples related to sorting