|
Home > Archive > Unix Shell > September 2006 > sort time complexity
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
sort time complexity
|
|
| Nirnimesh 2006-09-29, 7:28 am |
| What is the time complexity of the coreutils sort?
Nirnimesh
| |
| Kenny McCormack 2006-09-29, 7:28 am |
| In article <1159528055.176751.28970@h48g2000cwc.googlegroups.com>,
Nirnimesh <nirnimesh@gmail.com> wrote:
>What is the time complexity of the coreutils sort?
Will Brad dump Jennifer?
Tune in next time and see...
| |
| Janis Papanagnou 2006-09-29, 7:57 pm |
| Nirnimesh wrote:
> What is the time complexity of the coreutils sort?
>
>
> Nirnimesh
>
My guess would be n*log(n).
sort-1000 0m0,00s
sort-10000 0m0,08s
sort-100000 0m0,42s
sort-1000000 0m3,53s
sort-10000000 0m40,65s
Yes, seems quite so.
Janis
| |
| Loki Harfagr 2006-09-30, 7:31 am |
| Le Fri, 29 Sep 2006 22:54:50 +0200, Janis Papanagnou a écrit_:
> Nirnimesh wrote:
>
> My guess would be n*log(n).
>
> sort-1000 0m0,00s
> sort-10000 0m0,08s
> sort-100000 0m0,42s
> sort-1000000 0m3,53s
> sort-10000000 0m40,65s
>
> Yes, seems quite so.
>
> Janis
That should be right.
The coreutils sort uses qsort() that's like a wrapper to
different algorithms according to the type of data, it typically
will do a mergesort in many cases, chosling a quicksort for most
the rest, some types of data are "pre-translated" (eg months names)
Anyway ...
The mergesort and quicksort algorithms are two members of the
O(n*log(n)) family with sligthly different coefficients :-)
|
|
|
|
|