I recall some kind of sort that requires a construction of link list for storing index numbers of the original array. Only that the final link list (of index n

I recall some kind of sort that requires a construction of link list for storing index numbers of the original array. Only that the final link list (of index numbers) were in sorted order of which you then summarily write in the final array. Which would have consumed some (n*(row-size)+n*(link-ptr-size+value-size) memory outside of its original array. probably did O(n^1.5 for read operation which is WAY better than O(n^2) for bubble-sort. Best in-its class algorithm for swap at O(2), worst case? Delving into swap breakdown, its write operation might be O(3n+1) for writing a value then updating a link list pointer for each entry and for its link value into that final array; +1 for that NULL pointer at the end. was arguably the lowest O (way back then) but at extremely high cost of memory. Never did learn which sort class did that variant falls into. EDITED: insertion class, memory-hog-style.