The BinSort also requires space for the Heads and Tails of the Bins. This is usually not a substantial amount of space. The AddressCalculationSort requires space for M Heads and Tails, where M is the Range of keys. The version used here uses linked lists and has the same space overhead as the other LinkedList oriented sorts. This is almost always to be avoided.
Recursion can produce a large number of calls.
Recursive algorithms can usually be easily modified to avoid or simulate the recursion. The benefit is proportional to the overhead associated with the subprogram call. As you can see, the NONrecursive version runs a little faster, but the difference is almost negligible. On an algorithm which has a larger number of calls, or on a system which has larger CALL overhead, the difference would be larger. These sorts actually swap around an array of pointers rather than the array of records.