Skew binary smoothsort: - construct a forest of perfect binary trees, with the depth of consecutive nodes spread out in a fashion similar to 2-adic numbers (contrast to heapsort, which clumps all nodes of equal depth together) - turn the forest into a proper heap by sifting nodes down in a bottom-up fashion -repeatedly move largest root to end, delete (disregard) it from heap, restore heap property -alternatively, the building of the heap can also be thought of as iteratively merging the binary trees of increasing order, with special gaps between them (due to the def'n that every binary tree has a single root node at the end of it) adaptive for nearly sorted lists Heapsort: https://en.wikipedia.org/wiki/Heapsort simple heap indexing, sorting time for any list of fixed size stays relatively constant Jsort: - build a min-binary-heap, with root being first item in list - build max-heap from resulting list, now with root being last item - another way is to do min-heap, reverse the resulting list, and build a max-heap with root as first item, then reverse again; uses same index systems for parent/child - insertion sort final result
