Fibonacci Butt Sort

Let us discuss the various implementations of theFIBONACCI BUTT SORT.

>>208
You know I very nearly implemented a butt sort in befunge. Keeping track of state in befunge kinda blows, unless you're doing something like this:

v>>31g> ::51gg:2v++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
9p BXY|-+<v3*89<%+ *                                                      *   +
21 >98 *7^>+\-0|<+ *                                                     *    +
*5 ^:+ 1pg15\,:< + *                                                     ***  +
10^  <>$25*,51g1v+                                                            +
-^ p<| -*46p15:+<+                                                            +
31^> 151p>92*4v+                                                            +
 ^_ ".",   ^ vp1<+                                                            +
>v >41p      >0 v+                                                            +
:5! vg-1g15-1g14<+                                                            +
+1-+>+41g1-51gg+v+                                                            +
1p-1vg+1g15-1g14<+                                                            +
g61g>+41g51g1-g+v+                                                            +
14*1v4+g+1g15g14<+                           * *                              +
5>^4>1g1+51g1-g+v+                           * *                              +
^ _^v4+gg15+1g14<+                           ***                              +
>v! >1g1+51g1+g+v+                                                            +
g8-v14/*25-*4*88<+                                                            +
19+>g51gg" "- v  +                                                            +
4*5  v<   v-2:_3v+                                                            +
 >^   |!-3_$  v<-+                                                            +
^    < <      <|<+                                                         ***+
>g51gp ^ >51gp^>v+                                                            +
^14"+"<  ^g14"!"<++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
... which is kind of awesome.