Thread: 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
}