Date: Sun, 19 Mar 2017 22:20:22 +0100 From: Ed Schouten <ed@nuxi.nl> To: Darshan Sharma <thedarshansharma@gmail.com> Cc: Brooks Davis <brooks@freebsd.org>, hackers@freebsd.org Subject: Re: GSOC Project - "Replace mergesort implementation" Message-ID: <CABh_MKmvnJSd=wNvg6EJEm_Jwewua8fKOXOXOv3KGwtjMrmdVw@mail.gmail.com> In-Reply-To: <CA%2BMb7kBR933i6NURmuhuZm8Oq_6wmZw0gYJitKcggMXU--d9eQ@mail.gmail.com> References: <CA%2BMb7kBR933i6NURmuhuZm8Oq_6wmZw0gYJitKcggMXU--d9eQ@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CABh_MKmvnJSd=wNvg6EJEm_Jwewua8fKOXOXOv3KGwtjMrmdVw>