Messages in this thread | | | Date | Fri, 9 Mar 2001 08:46:17 -0500 | From | James Lewis Nance <> | Subject | Re: quicksort for linked list |
| |
On Fri, Mar 09, 2001 at 01:08:57PM +0530, Manoj Sontakke wrote: > Hi > Sorry, these questions do not belog here but i could not find any > better place. > > 1. Is quicksort on doubly linked list is implemented anywhere? I need it > for sk_buff queues.
I would suggest that you use merge sort. It is ideally suited for sorting linked lists, and it always has N log N running time. I dont know of an existing implementation in the kernel sources, but it should be easy to write one. I did a google search on "merge sort" "linked list" and it comes up with lots of links. Here is a good one:
http://www.ddj.com/articles/1998/9805/9805p/9805p.htm?topic=java
Hope this helps,
Jim - 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/
| |