lkml.org 
[lkml]   [2001]   [Mar]   [9]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: quicksort for linked list
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/

\
 
 \ /
  Last update: 2005-03-22 13:29    [W:0.108 / U:0.580 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site