[prev in list] [next in list] [prev in thread] [next in thread] 

List:       freebsd-hackers
Subject:    Re: GSOC Project - "Replace mergesort implementation"
From:       Ed Schouten <ed () nuxi ! nl>
Date:       2017-03-19 21:20:22
Message-ID: CABh_MKmvnJSd=wNvg6EJEm_Jwewua8fKOXOXOv3KGwtjMrmdVw () mail ! gmail ! com
[Download RAW message or body]

Hi Darshan,

2017-03-19 16:41 GMT+01:00 Darshan Sharma <thedarshansharma@gmail.com>:
> After going through all the projects I find that I can do - "Replacement of merge sort".

Nice!

When working on this, be sure to experiment with Block Sort / Grail Sort:

https://en.wikipedia.org/wiki/Block_sort
https://github.com/Mrrl/GrailSort

Basically it's a version of merge sort that uses an in-place list
merging algorithm. This means that end up with a sorting algorithm
that doesn't need to allocate any memory, but has the advantage over
qsort() that it's stable and has a worst-case running time of O(n log
n). That said, I don't know how expensive the in-place list merging
is.

-- 
Ed Schouten <ed@nuxi.nl>
Nuxi, 's-Hertogenbosch, the Netherlands
KvK-nr.: 62051717
_______________________________________________
freebsd-hackers@freebsd.org mailing list
https://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"
[prev in list] [next in list] [prev in thread] [next in thread]