Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Is stdlib's qsort recursive?

I've read that qsort is just a generic sort, with no promises about implementation. I don't know about how libraries vary from platform to plaform, but assuming the Mac OS X and Linux implementations are broadly similar, are the qsort implementations recursive and/or require a lot of stack?

I have a large array (hundreds of thousands of elements) and I want to sort it without blowing my stack to oblivion. Alternatively, any suggestions for an equivalent for large arrays?

like image 368
Joe Avatar asked Jul 31 '10 20:07

Joe


People also ask

Is qsort recursive?

Like merge sort, quicksort uses divide-and-conquer, and so it's a recursive algorithm. The way that quicksort uses divide-and-conquer is a little different from how merge sort does. In merge sort, the divide step does hardly anything, and all the real work happens in the combine step.

What sorting algorithm does qsort use?

As the name suggests, qsort function uses QuickSort algorithm to sort the given array, although the C standard does not require it to implement quicksort. C++ sort function uses introsort which is a hybrid algorithm. Different implementations use different algorithms.

Can quick sort be implemented without recursion?

yes quick sort can be implemented without recursion, no it cannot be implemented without any local automatic storage, yes only a constant amount of extra space is necessary, but only because we live is a small world where the maximum size of the array is bounded by available memory.

Is qsort the same as quicksort?

qsort() is a C standard library function. "Quicksort", on the other hand, is a specific sorting algorithm. It is often used as the backing algorithm of an actual implementation of qsort() .


2 Answers

Here's a version from BSD, copyright Apple, presumably used in OS X at some time or another:

http://www.opensource.apple.com/source/xnu/xnu-1456.1.26/bsd/kern/qsort.c

It is call-recursive, although the upper bound on the depth of recursion is small, as Blindy explains.

Here's a version from glibc, presumably used in Linux systems at some time or another:

http://www.umcs.maine.edu/~chaw/200801/capstone/n/qsort.c

It's not call recursive. For exactly the same reason that the limit on call-recursion is small, it can use a small fixed amount of stack to manage its loop-recursion.

Can I be bothered to look up the latest versions? Nope ;-)

For a few hundred thousand array elements, even the call-recursive implementation won't call more than 20 levels deep. In the grand scheme of things that is not deep, except on very limited embedded devices, which wouldn't have enough memory for you to have an array that big to sort in the first place. When N is bounded above, O(log N) obviously is a constant, but more than that it's normally quite a manageable constant. Usually 32 or 64 times "small" is "reasonable".

like image 171
Steve Jessop Avatar answered Oct 20 '22 17:10

Steve Jessop


You know, the recursive part is logn deep. In 64 levels of recursion (which is ~64*4=~256 bytes of stack total) you can sort an array of size ~2^64, ie an array as large as you can address on a 64 bit cpu, which is 147573952589676412928 bytes for 64 bit integers. You can't even hold it in memory!

Worry about stuff that matters imo.

like image 38
Blindy Avatar answered Oct 20 '22 15:10

Blindy