vector<int> quickSort(vector<int> arr) {
    vector<int> left, equal, right;
    for(int i = 0; i < arr.size(); i++){
        if(arr[i] < arr[0]) left.push_back(arr[i]);
        else if(arr[i] > arr[0]) right.push_back(arr[i]);
        else equal.push_back(arr[i]);
    }
    left.insert(left.end(), equal.begin(), equal.end());
    left.insert(left.end(), right.begin(), right.end());
    return left;
}

public static List<Integer> quickSort(List<Integer> arr) {
        if(arr.size() == 1) return arr; //already sorted
        
        int pivot = arr.get(0); // pivot is always arr[0]
        //declare each subarray
        List<Integer> left = new ArrayList<>();
        List<Integer> right = new ArrayList<>();
        List<Integer> equal = new ArrayList<>();
        
        //partition the og arr
        for(int element : arr){
            if(element < pivot) left.add(element);
            else if (element > pivot) right.add(element);
            else equal.add(element);
        }
        
        //combine the subarrays
        List<Integer> combinedList = 
            Stream.of(left, equal, right)
            .flatMap(List::stream)
            .collect(Collectors.toList());
        return combinedList;
    }

public static List<Integer> quickSort(List<Integer> arr) {
    // Write your code here
    int n = arr.size();
    List<Integer> left = new ArrayList<>();
    List<Integer> right = new ArrayList<>();
    List<Integer> equal = new ArrayList<>();
    int p = arr.get(0);
    for(int i = 0; i < n; i++) {
        if(p > arr.get(i)) {
            left.add(arr.get(i));
        } else if (p < arr.get(i)) {
            right.add(arr.get(i));
        } else {
            equal.add(arr.get(i));
        }
    }
    List<Integer> result = new ArrayList<>();
    result.addAll(left);
    result.addAll(equal);
    result.addAll(right);
    return result;
    }

def quickSort(arr):
    pivot = arr[0]
    arr.remove(pivot)
    array = [pivot]
    for num in arr:
        if num <= pivot:
            array.insert(array.index(pivot), num)
        else:
            array.append(num)
    return array