Suggestions on how to better write a quicksort function?

Hi! I'm a first semester computer science student, and i'm working on an extra credit assignment for my C++ class (although the code below is in C, it should be portable to C++). The assignment is to write a quicksort function using in-place sorting. I already have a working function below, however, I'd like to make it more efficient, if possible.

At first, I considered using an internal stack rather than recursion, however I'm not sure if that would be the best way to go about it, considering I would have to allocate twice the memory occupied by the array itself in order to create enough stack space for a worst-case scenarion, not to mention that would require stdlib.h, and I'm trying to avoid using libraries if possible. However, I am concerned that, using recursion, this function could possibly overload the execution stack and collapse the universe into a singularity.

Anyway, I'm open to criticism, be it constructive or purely vitriolic. Thanks!

Code:

void __qs_sw(int* a, int* b)
{
	int s = *a;
	*a = *b;
	*b = s;
}

// quicksort(int* arr, unsigned nm)
// int* arr:	the pointer to the beginning of your array
// int nm:	the number of members in your array
//
// example:
// int arr[] = { 33, -33, 2124, 99, -1000, 40, 27, 99, 30 };
// quicksort(arr, sizeof(arr) / sizeof(int));
extern void quicksort(int* arr, unsigned nm)
{
	int lp=1, rp = nm - 1;					// initialize the pointers at the left and right sides of the array
	while (lp < rp)						// loop until the pointers collide
		if (arr[lp] > arr[0] && arr[rp] < arr[0])	// if the left side is greater and the right side is lesser,
			__qs_sw(&arr[lp++], &arr[rp--]);	// swap the values
		else if (arr[lp] <= arr[0])			// otherwise, if the left side is greater
			lp++;					// increment the left pointer
		else						// otherwise, if the right side is lesser
			rp--;					// decrement the right side pointer
	if (arr[lp] > arr[0])					// now, compare the last value the left pointer is sitting on to the pivot
		lp--;						// if it's greater than the pivot, decrement lp (which is now the target to swap the pivot into) 
	__qs_sw(&arr[lp], &arr[0]);				// now, swap the pivot into its new target home
	if (lp > 1)						// if we have more than one left-side member,
		quicksort(arr, lp);				// sort the left-side sub-array
	if (nm - lp > 2)					// if we have more than one right-side member,
		quicksort(&arr[lp + 1], nm - lp - 1);		// sort the right-side sub-array
}

using the name __qs_sw is not great, as names starting with __ are reserved for the compiler/library implementation. Instead of using a reserved name, use static to ensure it isn't exported.

Technically, rp and lp aren't pointers, they're indices. For efficiency, you may actually want to make them pointers.

extern on a function definition is meaningless. the nm should be size_t instead of unsigned.

--
Mats

Your partitioning loop is non-optimal in terms of the number of comparisons. The first if-statment tests arr[lp] > arr[0] but given that the result of that individual test isn't remembered, you are forcing yourself to test the same thing again in arr[lp] <= arr[0].
The usual way to do it is to have two while loops inside the partitioning loop. One of them advances lp while it points to an item less than the splitter, and the other one decrements rp while it is not less than the splitter.

The other slightly more advanced way of optimising it is to only recurse one the smaller portion after the partitioning, and loop on the other portion instead. This also protects it against maliciously crafted input which would otherwise cause stack overflow.

Why pass in nm as unsigned but then assign it to a signed int? Don't mix them unless you have to.
Note that if you change rp to unsigned you'll have to do a little work to make sure it doesn't explode for sorting zero items.