WikiSort – Fast, stable, O(1) space merge sort algorithm

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by _delirium on Saturday March 15, 2014 @09:04PM (#7407326)

It's irrelevant in practice, mostly because log(n) is very small for essentially all values of n, so one could consider it "close enough to constant". Close enough in the sense that a reasonably small constant (like "64") bounds any value of it you could possibly encounter in a sorting algorithm. But that's true of many things in big-O analysis.

If your temporary space was used by some indices represented as unary-encoded integers (which take O(n) space), it'd suddenly be harder to ignore the indices, because O(n) is not "very small" for many commonly encountered sizes of n. So I don't think taking the temporary space used by indexing into account is conceptually wrong, it just happens not to matter here because log(n) factors often don't matter.

[ Parent | on HN ]

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by makomk on Sunday March 16, 2014 @07:15AM (#7409016)

In practice, though, it makes sense in this case to assume integers representing array indices are constant-space and arithmetic on them takes constant time. The computers we're running these algorithms on use base 2 and the size of integer they can operate on in a single operation has scaled nicely with the amount of storage they have access to.

[ Parent | on HN ]