Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C# DSA implementation can be compared directly with the other languages.

Basic Implementation

basic.cs

using System;

class Program {
	static void Main() {
		int[] arr = new int[] { 4, 1, 5, 2, 3 };
		QuickSort(arr, 0, arr.Length - 1);
		PrintArray(arr);
	}

	static void PrintArray(int[] arr) {
		Console.Write("[");
		for (int i = 0; i < arr.Length; i++) {
			if (i > 0) Console.Write(", ");
			Console.Write(arr[i]);
		}
		Console.WriteLine("]");
	}
	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++;
				int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
			}
		}
		int swap = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = swap;
		return i + 1;
	}

	static void QuickSort(int[] arr, int low, int high) {
		if (low < high) {
			int pivotIndex = Partition(arr, low, high);
			QuickSort(arr, low, pivotIndex - 1);
			QuickSort(arr, pivotIndex + 1, high);
		}
	}
}

Complexity

Time: O(n^2) worst, O(n log n) average
Space: O(log n) average call stack
Stable: no

Implementation notes

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

pivot The final element is moved to the boundary between smaller and larger values.

partition One scan rearranges the current range before the recursive calls.