Código de ordenação em awk.

• bubble sort

  function bubble_sort(arr, a, b,     i,done,t) {
      i = a
      done = 1
      for (;;) {
          if (i == b) {
              if (done)
                  break
              i = a
              done = 1
          }
          if (arr[i] > arr[i+1]) {
              t = arr[i]
              arr[i] = arr[i+1]
              arr[i+1] = t
              done = 0
          }
          i = i+1
      }
  }
  
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { bubble_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• heap sort

  ## works only on arrays indexed [1..n]
  
  function heap_sort(arr, n,  i,t) {
      make_heap(arr, n)
      for (i=n; i>1; i--) {
          t = arr[1]
          arr[1] = arr[i]
          arr[i] = t
          sift_down(arr, i-1, 1)
      }
  }
  
  function make_heap(arr, n,  i) {
      for (i=int(n/2); i>=1; i--)
          sift_down(arr, n, i)
  }
  
  function sift_down(arr, n, i,   k,j,t) {
      k = i
      do {
          j = k
          if (2*j <= n && arr[2*j] > arr[k])
              k = 2*j
          if (2*j < n && arr[2*j+1] > arr[k])
              k = 2*j+1
          t = arr[j]
          arr[j] = arr[k]
          arr[k] = t
      } while (j != k);
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { heap_sort(x, n); for (i=1; i<=n; i++) print x[i] }

• insert sort

  # sorts array ARR[A..B]
  function insert_sort(arr, a, b,     i,j,t) {
      for (i=a+1; i<=b; i++) {
          if (arr[i] > arr[i-1])
              continue
          t = arr[i]
          j=i-1
          do 
              arr[j+1] = arr[j]; 
          while (--j>0 && t < arr[j]);
          arr[j+1] = t
      }
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { insert_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• merge sort

  function merge_sort(arr, a, b,      k) {
      if (a<b) {
          k = int((a+b)/2)
          merge_sort(arr, a, k)
          merge_sort(arr, k+1, b)
          merge(arr,a,k,b)
      }
  }
  
  function merge(arr, a, k, b,    i,j,p,c) {
      j = i = a
      p = k+1
      while (a <= k && p <= b) {
          if (arr[a] <= arr[p]) {
              c[i++] = arr[a++]
          } else {
              c[i++] = arr[p++]
          }
      }
      while (a <= k) c[i++] = arr[a++]
      while (p <= b) c[i++] = arr[p++]
  
      while (j<=b) {
          arr[j] = c[j]
          j++
      }
  }
  
  ## main
  function pr(arr,i,j) { while (i<=j) print arr[i++] }
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { merge_sort(x, 1, i); pr(x, 1, i); }

• quick sort

  function quick_sort(arr, a, b,      pivot,i,j,t) {
  
      if (a >= b)
          return 
  
      if (a+1 == b) {
          if (arr[a] > arr[b]) {
              t = arr[a]
              arr[a] = arr[b]
              arr[b] = t
          }
          return 
      }
  
      pivot = median(arr[a], arr[b], arr[int((a+b)/2)])
      i = a-1; 
      j = b+1; 
      for (;;) {
          while (arr[++i] < pivot)
              ; 
          while (arr[--j] > pivot)
              ; 
  
          if (i>=j)
              break
  
          t = arr[i]
          arr[i] = arr[j]
          arr[j] = t
      }
      quick_sort(arr, a, i-1)
      quick_sort(arr, i, b)
  }
  
  function median(a, b, c) {
      if (a<b) {
          if (b<c)
              return c
          if (a<c)
              return c
          return a
      }
      if (a<c)
          return c
      if (b<c)
          return c
      return b
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { quick_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }

• selection sort

  # sorts array ARR[A..B]
  function selection_sort(arr, a, b,      i,j,k,t) {
      for (i=a; i<=b; i++) {
          k=i
          for (j=i+1; j<=b; j++) {
              if (arr[k] > arr[j]) 
                  k = j
          }
          if (k != i) {
              t = arr[i]
              arr[i] = arr[k]
              arr[k] = t
          }
      }
  }
  
  # main
  { x[++n] = substr($0,1) } ## lexical sort
  #{ x[++n] = $0+0 } ## numerical sort
  END { selection_sort(x, 1, n); for (i=1; i<=n; i++) print x[i] }