Sort: Counting sort

Context

Counting sort is a sort algorithm dedicated to lists having values in a small set. Then, one can create an array of same size and store values (or count) while reading.
Using BrainFuck, all our values are stored between 0 and 255. Therefore, it might be an interesting sort algorithm. Let's implement it.
Initial state

• Memory: 0 0 [array] 0 0 0 0 0 ... where array is a 2 cells block array of nullable integers
• Pointer: just after array
• Input: any

Process

• Generate counter array
• That's a 2 cells block array of nullable integers, of size 256
• Generate the first cell
• Then have 255 in a counter and generate all cells after
• For each integer N from the list
• Access item N in array and increment counter
• Optionally, we can rebuild back the array when sort is completed
• Define current value (initially: 0)
• For each counter C in counter array
• Add current value C times
• Increment current value

Code - try it

generate counter array: 2 cells array with 256 items
->>>>>+<<<<<[->>>>>[>>]+[<<]<<<]

read integers one by one and store into array
go to first integer and loop
<<[<<]>>
[
  remove cell indicator
  -
  move value to end
  >[->[>>]>+<<<[<<]>]
  go to value and move backward
  >[>>]>[-<+>]
  access array cell given by index
  <[->>>[>>]+>>->[-<<+>>]<<<[<<]<]
  increment count for given value
  >>>[>>]>>>+
  move array back to position
  <<<<<[[->>+<<]>[->>+<<]<<<]
  go to next integer
  <<<[<<]>>
]

rebuild array of values
>>>>>
[
  move cell
  -<<+>>>[-<<+>>]<<
  add value N that many times
  [
    -
    go to current value
    <[<<]<
    copy / move to end of array
    [->+>+<<]>[-<<<[<<]>+>[>>]>]
    set cell flag
    <<<[<<]+[>>]
    restore current value copy
    >>[-<<+>>]
    go back to value counter
    >[>>]<
  ]
  increment current value
  <[<<]<+
  >>>[>>]>>
  go to next cell and loop
]

clear counter array
<<<<[->[-]<<<]

Final state

• Memory: 0 0 [sorted array] 0 0 0...
• Cursor: 2 cells after array
• Input: unchanged
• Output: unchanged

Notes

1. Due to our array rebuild, the sort is descending, but this can be easily changed to ascending sort
2. Despite a shorter algorithm, execution is really longer than Quicksort