Master Quick Sort - O(n log n) Divide & Conquer

function quickSort(arr, low = 0, high = arr.length - 1) {
    /**
     * Quick Sort with Lomuto partition scheme
     * Time: O(n log n) average, O(n²) worst
     * Space: O(log n) recursion stack
     */
    if (low < high) {
        // Partition and get pivot index
        const pi = partition(arr, low, high);

        // Recursively sort left and right
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
    return arr;
}

function partition(arr, low, high) {
    // Choose last element as pivot
    const pivot = arr[high];
    let i = low - 1;  // Partition index

    for (let j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            [arr[i], arr[j]] = [arr[j], arr[i]];
        }
    }

    // Place pivot in correct position
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
}

// Usage
const arr = [64, 34, 25, 12, 22, 11, 90];
console.log(quickSort(arr));  // [11, 12, 22, 25, 34, 64, 90]

package main

import "fmt"

// QuickSort sorts the array using quick sort algorithm
// Time: O(n log n) average, O(n²) worst
// Space: O(log n) recursion stack
func QuickSort(arr []int, low, high int) {
    if low < high {
        // Partition and get pivot index
        pi := partition(arr, low, high)

        // Recursively sort left and right
        QuickSort(arr, low, pi-1)
        QuickSort(arr, pi+1, high)
    }
}

func partition(arr []int, low, high int) int {
    // Choose last element as pivot
    pivot := arr[high]
    i := low - 1  // Partition index

    for j := low; j < high; j++ {
        if arr[j] <= pivot {
            i++
            arr[i], arr[j] = arr[j], arr[i]
        }
    }

    // Place pivot in correct position
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1
}

func main() {
    arr := []int{64, 34, 25, 12, 22, 11, 90}
    QuickSort(arr, 0, len(arr)-1)
    fmt.Println(arr)  // [11 12 22 25 34 64 90]
}

public class QuickSort {
    /**
     * Quick Sort with Lomuto partition scheme
     * Time: O(n log n) average, O(n²) worst
     * Space: O(log n) recursion stack
     */
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition and get pivot index
            int pi = partition(arr, low, high);

            // Recursively sort left and right
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // Choose last element as pivot
        int pivot = arr[high];
        int i = low - 1;  // Partition index

        for (int j = low; j < high; j++) {
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Place pivot in correct position
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}

#include <iostream>
#include <vector>
using namespace std;

/**
 * Quick Sort with Lomuto partition scheme
 * Time: O(n log n) average, O(n²) worst
 * Space: O(log n) recursion stack
 */
int partition(vector<int>& arr, int low, int high) {
    // Choose last element as pivot
    int pivot = arr[high];
    int i = low - 1;  // Partition index

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    // Place pivot in correct position
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        // Partition and get pivot index
        int pi = partition(arr, low, high);

        // Recursively sort left and right
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
    quickSort(arr, 0, arr.size() - 1);

    for (int x : arr) cout << x << " ";
    return 0;
}

/// Quick Sort with Lomuto partition scheme
/// Time: O(n log n) average, O(n²) worst
/// Space: O(log n) recursion stack
fn quick_sort(arr: &mut [i32], low: isize, high: isize) {
    if low < high {
        // Partition and get pivot index
        let pi = partition(arr, low, high);

        // Recursively sort left and right
        quick_sort(arr, low, pi - 1);
        quick_sort(arr, pi + 1, high);
    }
}

fn partition(arr: &mut [i32], low: isize, high: isize) -> isize {
    // Choose last element as pivot
    let pivot = arr[high as usize];
    let mut i = low - 1;  // Partition index

    for j in low..high {
        if arr[j as usize] <= pivot {
            i += 1;
            arr.swap(i as usize, j as usize);
        }
    }

    // Place pivot in correct position
    arr.swap((i + 1) as usize, high as usize);
    i + 1
}

fn main() {
    let mut arr = vec![64, 34, 25, 12, 22, 11, 90];
    let len = arr.len();
    quick_sort(&mut arr, 0, (len - 1) as isize);
    println!("{:?}", arr);  // [11, 12, 22, 25, 34, 64, 90]
}