News for hackers. Stuff that matters.

A comment on WikiSort – Fast, stable, O(1) space merge sort algorithm. Parent comment

Re:WikiSort – Fast, stable, O(1) space merge sort algorithm by tbingmann on Saturday March 15, 2014 @02:44PM (#7405694)
In a nutshell: to keep an index into an array of size n requires log_2(n) bits. Thus any algorithm, which keeps even just one index into the input takes Omega(log n) space. Yay for pedantic asymptotics.
[ Parent | on HN ]

There are no comments on this comment yet.