Quicksort

Challenge

Sort an int array ascending in place using recursive partitioning around a pivot.

Task

Implement void quicksort(int *a, size_t n) that sorts the first n elements of a ascending, in place, using a partitioning scheme of your choice (Lomuto or Hoare). No main — the grader calls it.

Input

• a: pointer to a writable int array.
• n: the number of elements (may be 0).

Output

Nothing is returned. After the call a[0..n-1] is sorted ascending.

Example

{5,2,8,1,9,3,7,4,6}   ->   {1,2,3,4,5,6,7,8,9}
{9,8,7,6,5,4,3,2,1}   ->   {1,2,3,4,5,6,7,8,9}
{3,3,3,3}             ->   {3,3,3,3}

Edge cases

• Empty and single-element arrays need no work (watch the n < 2 base case).
• Duplicates and already-reversed inputs must still sort correctly.

Rules

• Sort in place; partition around a pivot and recurse on each side.

Input format

Pointer a to a writable int array and a length n (n may be 0).

Output format

Nothing returned; a is sorted ascending in place.

Constraints

Sort in place via recursive partitioning; handle the n < 2 base case.

Starter code

#include <stddef.h>

void quicksort(int *a, size_t n) {
    /* TODO */
}