linsort - 22
Lin / Devi
Consider A[i], A[j]. Assume w.o.l.o.g, A[i] A[j].
Then, n A[i] n A[j].
So, A[i] is placed into the same bucket as A[j] or into a bucket with a lower index.
If same bucket, insertion sort fixes up.
If earlier bucket, concatenation of lists fixes up.