Generic quicksort library that can be used to sort an array having any data type (int, char *, struct key_value *, etc.).

[Collin Funk]

Amit <amitchoudhary0523@gmail.com> writes:

>>
>> >> [1]
>> https://pubs.opengroup.org/onlinepubs/9799919799/functions/qsort.html
>> >
>> >
>> > This is fine with me. But then why name it qsort(). Why not call it
>> sort().
>> >
>> > Anyways, anyone who sees qsort() will assume that it is quicksort.
>> >
>> > Anyways, there is no point in debating about the name of the function.
>>
>> Because that is what the standard requires that the function is named.
>>
>> Most users will care how it performs in the typical use case, not what
>> algorithm is used under the hood.
>>
>> Collin
>>
>
> I don't know about other users but for sorting I would want to know which
> algorithm is being used.
>
> So, if both quicksort and mergesort options are there, then I will choose
> quicksort because it has no extra memory requirements.
>
> Mergesort will most probably fail if the array has 1 billion single byte
> elements because getting 500 MB of memory may fail.
>
> And since linux has optimistic/aggresive memory allocation then it is quite
> possible that when mergesort actually uses the whole 500 MB memory then OOM
> may come in picture and kill some other program.
>
> Mergesort is actually not good compared to quicksort because of memory
> requirements.

As Adhemerval mentioned the rational can be found in the 'git log' or on
the mailing list archives [1].

There are programs that expect the sorting to be stable. I have never
run into a program running out of memory using qsort.

Collin

[1] https://inbox.sourceware.org/libc-alpha/a0b8e28438edc5295b33ac280325847314ae7dcc.camel@xry111.site/T/#m2646a2c7a392ef12791a53ddf39db260358768cb