C# Program to Implement Quick Sort Algorithm

A C# quick sort program uses a QuickSort method that picks a pivot, partitions the array, and recursively sorts subarrays; for example, QuickSort(arr, 0, arr.Length - 1); sorts the entire array in place.

Examples

Input[3, 1, 4, 1, 5]

Output[1, 1, 3, 4, 5]

Input[10, 7, 8, 9, 1, 5]

Output[1, 5, 7, 8, 9, 10]

Input[]

Output[]

How to Think About It

To sort an array using quick sort, choose a pivot element and rearrange the array so that elements smaller than the pivot come before it and larger ones come after. Then, apply the same process to the left and right parts until the whole array is sorted.

Algorithm

1

Pick the last element as pivot.

2

Partition the array so elements less than pivot are left, greater are right.

3

Recursively apply quick sort to left subarray.

4

Recursively apply quick sort to right subarray.

5

Stop when subarray has zero or one element.

Code

csharp

using System;
class QuickSortProgram {
    static void QuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = Partition(arr, low, high);
            QuickSort(arr, low, pi - 1);
            QuickSort(arr, pi + 1, high);
        }
    }

    static int Partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;
    }

    static void Main() {
        int[] arr = {10, 7, 8, 9, 1, 5};
        QuickSort(arr, 0, arr.Length - 1);
        Console.WriteLine(string.Join(", ", arr));
    }
}

Output

1, 5, 7, 8, 9, 10

Dry Run

Let's trace sorting the array [10, 7, 8, 9, 1, 5] through the quick sort code.

1

Initial call

QuickSort called with low=0, high=5, array=[10,7,8,9,1,5]

2

Partitioning

Pivot=5; elements less than 5 moved left; array becomes [1, 7, 8, 9, 10, 5]

3

Pivot position

Pivot 5 placed at index 1; array=[1,5,8,9,10,7]

4

Recursive calls

QuickSort called on left subarray [1] and right subarray [8,9,10,7]

5

Sorting right subarray

Pivot=7; after partition array=[1,5,7,9,10,8]

6

Final sorted array

[1,5,7,8,9,10]

Step	Array State	Pivot	Action
1	[10,7,8,9,1,5]	5	Start partition
2	[1,7,8,9,10,5]	5	Swap 10 and 1
3	[1,5,8,9,10,7]	5	Place pivot at index 1
4	[1,5,8,9,10,7]	7	Partition right subarray
5	[1,5,7,9,10,8]	7	Place pivot at index 2
6	[1,5,7,8,9,10]	-	Sorted array

Why This Works

Step 1: Choosing a pivot

The pivot divides the array into smaller and larger parts, helping to sort by comparison.

Step 2: Partitioning

Elements less than pivot move left, greater move right, so pivot ends in correct place.

Step 3: Recursion

Sorting left and right parts separately repeats the process until fully sorted.

Alternative Approaches

Iterative Quick Sort

csharp

using System;
class IterativeQuickSort {
    static void QuickSortIterative(int[] arr, int l, int h) {
        int[] stack = new int[h - l + 1];
        int top = -1;
        stack[++top] = l;
        stack[++top] = h;
        while (top >= 0) {
            h = stack[top--];
            l = stack[top--];
            int p = Partition(arr, l, h);
            if (p - 1 > l) {
                stack[++top] = l;
                stack[++top] = p - 1;
            }
            if (p + 1 < h) {
                stack[++top] = p + 1;
                stack[++top] = h;
            }
        }
    }

    static int Partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;
        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                (arr[i], arr[j]) = (arr[j], arr[i]);
            }
        }
        (arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
        return i + 1;
    }

    static void Main() {
        int[] arr = {10, 7, 8, 9, 1, 5};
        QuickSortIterative(arr, 0, arr.Length - 1);
        Console.WriteLine(string.Join(", ", arr));
    }
}

Uses a stack instead of recursion to avoid stack overflow on large arrays.

Using LINQ (not in-place)

csharp

using System;
using System.Linq;
class QuickSortLINQ {
    static int[] QuickSort(int[] arr) {
        if (arr.Length <= 1) return arr;
        int pivot = arr[arr.Length / 2];
        var left = arr.Where(x => x < pivot).ToArray();
        var middle = arr.Where(x => x == pivot).ToArray();
        var right = arr.Where(x => x > pivot).ToArray();
        return QuickSort(left).Concat(middle).Concat(QuickSort(right)).ToArray();
    }

    static void Main() {
        int[] arr = {10, 7, 8, 9, 1, 5};
        var sorted = QuickSort(arr);
        Console.WriteLine(string.Join(", ", sorted));
    }
}

Simpler code but uses extra memory and is slower for large arrays.

Complexity: O(n log n) average, O(n^2) worst time, O(log n) average due to recursion stack space

Time Complexity

Quick sort divides the array and sorts subarrays recursively, leading to average O(n log n) time. Worst case O(n^2) happens when pivot is always smallest or largest.

Space Complexity

Quick sort sorts in place but uses recursion stack, which is O(log n) on average.

Which Approach is Fastest?

Recursive quick sort is fast and memory efficient; iterative avoids recursion stack but is more complex; LINQ approach is simpler but slower and uses extra memory.

Approach	Time	Space	Best For
Recursive Quick Sort	O(n log n) avg	O(log n)	General use, fast and memory efficient
Iterative Quick Sort	O(n log n) avg	O(n)	Avoid recursion stack overflow
LINQ Quick Sort	O(n log n) avg	O(n)	Simple code, small arrays