Off Topic 
Gravitysort
1 
Offline
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function swap(l, a, b) local tmp = l[a] l[a] = l[b] l[b] = tmp return l end function gravitysort(l, i, j) if not i then i = 1 end if not j then j = #l end if l[j] < l[i] then swap(l, i, j) end if j-i > 1 then local t = math.ceil((j-i)/6) gravitysort(l, i, j-t) gravitysort(l, i+t, j) gravitysort(l, i, j-t) gravitysort(l, i+t, j) gravitysort(l, i, j-t) gravitysort(l, i+t, j) end return l end
Bonus points if you can find the average order of magnitude of the running time.
(assume list index is O(1), math operations O(1), swap O(1), etc so that visiting every element is O(n) as the residual)