On Fri, 9 Mar 2001, Rogier Wolff wrote:
> Quicksort however is an algorithm that is recursive. This means that
> it can use unbounded amounts of stack -> This is not for the kernel.
It is of course bounded by the input size, but yes, it can use O(n)
additional memory in the worst case. There's no particular reason this
memory has to be on the stack - it's just convenient.
> Isn't it easier to do "insertion sort": Keep the lists sorted, and
> insert the item at the right place when you get the new item.
Assuming you get your items in sorted order, this is also O(N^2).
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
This archive was generated by hypermail 2b29 : Thu Mar 15 2001 - 21:00:10 EST