Implement QuickSort in BrainF*** As discussed in the Lounge room on Stack Overflow:


  if you can't implement the Quicksort algorithm given en.wikipedia.org/wiki/Quicksort in any language you have minimal knowledge of, you might want to consider a different profession. @sbi


but SBI also noted that maybe BrainF*** was an exception.

So, here's the puzzle/challenge: implement QuickSort in BrainF***. The implementation must


be interpreted by this and/or by the interpreter(s) here (for large scripts)
implement the algorithm as described on Wikipedia - if possible as an in-place sort
sort the following list of integers: [0,4,6,4,2,3,9,2,3,6,5,3] and print the result
BrainF* (697 bytes)

&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;,[&gt;,]&lt;[[&gt;&gt;&gt;+&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]&lt;+&lt;]&gt;[&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-]&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;[[&gt;&gt;+
&gt;+&gt;&gt;+&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;&lt;+&gt;&gt;-]&lt;[&gt;+&gt;&gt;+&gt;&gt;+&lt;&lt;&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]&gt;&gt;&gt;&gt;[-&lt;-&gt;]+&lt;[&gt;-&gt;+&lt;&lt;-[&gt;&gt;-
&lt;&lt;[-]]]&gt;[&lt;+&gt;-]&gt;[&lt;&lt;+&gt;&gt;-]&lt;+&lt;[-&gt;-&lt;&lt;[-]&lt;[-]&lt;&lt;[-]&lt;[[&gt;+&lt;-]&lt;]&gt;&gt;[&gt;]&lt;+&gt;&gt;&gt;&gt;]&gt;[-&lt;
&lt;+[-[&gt;+&lt;-]&lt;-[&gt;+&lt;-]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-]&lt;&lt;&lt;&lt;&lt;&lt;]&lt;&lt;[&gt;&gt;+&lt;&lt;-]&gt;[&gt;[&gt;+&gt;
&gt;+&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]&gt;&gt;&gt;&gt;&gt;&gt;[&lt;+&lt;+&gt;&gt;-]&lt;[&gt;+&lt;-]&lt;&lt;&lt;[&gt;+&gt;[&lt;-]&lt;[&lt;]&gt;&gt;[&lt;&lt;+&gt;[-]+&gt;-]&gt;-&lt;&lt;-
]&gt;&gt;[-]+&lt;&lt;&lt;[-&gt;&gt;+&lt;&lt;]&gt;&gt;[-&gt;-&lt;&lt;&lt;&lt;&lt;[&gt;+&lt;-]&lt;[&gt;+&lt;-]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-]
&lt;&lt;]&gt;[[-]&lt;&lt;&lt;&lt;&lt;&lt;[&gt;&gt;+&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;&lt;+&gt;&gt;-]&gt;&gt;&gt;&gt;&gt;[-[&gt;&gt;[&lt;&lt;&lt;+&gt;&gt;&gt;-]&lt;[&gt;+&lt;-]
&lt;-[&gt;+&lt;-]&gt;]&lt;&lt;[[&gt;&gt;+&lt;&lt;-]&lt;]]&gt;]&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;[&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;-]&lt;&lt;[[&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;
-]&gt;[&lt;+&gt;-]&lt;+&lt;]&lt;[[&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;+&gt;-]&lt;+&lt;&lt;]&gt;+&gt;[&lt;-&lt;&lt;[&gt;+&lt;-]&lt;[&lt;]&gt;[[&lt;
+&gt;-]&gt;]&gt;&gt;&gt;[&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;-]&lt;&lt;[&lt;+&gt;-]&gt;&gt;]&lt;[-&lt;&lt;+&gt;&gt;]&gt;&gt;&gt;]&lt;&lt;&lt;&lt;&lt;&lt;]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[.&gt;]


Below is an annotated version.  In order to keep track of what was supposed to be happening while developing it, I used a comment notation that looks like this: |a|b=0|c=A0|@d|A0|A1|```|

|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)


The memory is laid out with a left-growing stack of partitions to process  on the left, a scratch space in the center, and the array being sorted to the right.   Array indexing is handled by moving a "data bus" containing the index and working space through the array.
So for instance a 3-wide bus of |i|data|0|A0|A1|A2, will become |A0|i-1|data|0|A1|A2 after shifting by one.  The partitioning is performed by keeping the bus between the high and low elements.
Here's the full version:

Get input
&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt; ,[&gt;,]                      |A0|A1|```|An|@0|
Count items
&lt;[ [&gt;&gt;&gt;+&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]&lt;+ &lt;]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
&gt;[&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;[
  Copy K1 to a&amp;c via Z
  [&gt;&gt;+&gt;+&gt;&gt;+&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;&lt;+&gt;&gt;-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&amp;d via Z
  &lt;[&gt;+&gt;&gt;+&gt;&gt;+&lt;&lt;&lt;&lt;&lt;-]&gt;[&lt;+&gt;-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  &gt;&gt;&gt;&gt;[-&lt;-&gt;]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +&lt;[&gt;- &gt;+&lt;&lt;-[&gt;&gt;-&lt;&lt;[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  &gt;[&lt;+&gt;-]&gt;[&lt;&lt;+&gt;&gt;-]&lt;+&lt;      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [-&gt;-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    &lt;&lt;[-]&lt;[-]&lt;&lt;[-]&lt;[[&gt;+&lt;-]&lt;]&gt;&gt;[&gt;]&lt;+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  &gt;&gt;&gt;&gt;]&gt;[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    &lt;&lt;+[ -[&gt;+&lt;-]&lt;-[&gt;+&lt;-]&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;      (dec J as we move)
      [&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-]&lt;&lt;&lt;&lt;&lt;&lt; ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    &lt;&lt;[&gt;&gt;+&lt;&lt;-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    &gt;[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      &gt;[&gt;+&gt;&gt;+&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      &gt;&gt;&gt;&gt;&gt;&gt;[&lt;+&lt;+&gt;&gt;-]&lt;[&gt;+&lt;-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g 
      &lt;&lt;&lt;[ &gt;+&gt;[&lt;-]&lt;[&lt;]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g 
        &gt;&gt;[&lt;&lt;+&gt;[-]+&gt;-]&gt;-&lt;&lt;-]
      set g to 1; if d: set f 
      &gt;&gt;[-]+&lt;&lt;&lt; [-&gt;&gt;+&lt;&lt;]
      If Aq LT Ap move Aq across Bus
      &gt;&gt;[-&gt;- &lt;&lt;&lt;&lt;&lt;[&gt;+&lt;-] &lt;[&gt;+&lt;-] &gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;
        [&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;-] &lt;&lt;]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq                
      &gt;[[-] &lt;&lt;&lt;&lt;&lt;&lt;[&gt;&gt;+&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;&lt;+&gt;&gt;-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      &gt;&gt;&gt;&gt;&gt;[-
        &amp; While J shuttle right
        [&gt;&gt;[&lt;&lt;&lt;+&gt;&gt;&gt;-]&lt;[&gt;+&lt;-]&lt;-[&gt;+&lt;-]&gt;] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        &lt;&lt;[ [&gt;&gt;+&lt;&lt;-] &lt; ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]&gt;]
    Either bus moved or last element swapped; reduce J in either case
    &lt;&lt;&lt;&lt;&lt;&lt;-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    &gt;[&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    &lt;&lt;[ [&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;[&lt;+&gt;-]&lt;+ &lt;]     
    &lt;[ [&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;+&lt;&lt;&lt;&lt;&lt;&lt;&lt;&lt;-]&gt;&gt;[&lt;+&gt;-]&lt;+ &lt;&lt;] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    &gt;+&gt;[&lt;-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      &lt;&lt;[&gt;+&lt;-] &lt;[&lt;]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p| 
      shift left until return to 0 at K0;
      &gt;[ [&lt;+&gt;-] &gt;]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      &gt;&gt;&gt;[&lt;&lt;&lt;&lt;+&gt;&gt;&gt;&gt;-]&lt;&lt;[&lt;+&gt;-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty) 
    &gt;&gt;]&lt;[- &lt;&lt;+&gt;&gt;]              
  &gt;&gt;&gt;]  End if !empty
&lt;&lt;&lt;&lt;&lt;&lt;] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;&gt;[.&gt;]