let arr = [8, 4, 3, 2, 6, 7, 1, 5, 9]

function quickSort(arr) {
    console.log(arr)
    if(arr.length <= 1)
        return arr
    let midIndex = parseInt(arr.length / 2)
    let midValue = arr.splice(midIndex, 1)[0]
    let left = [], right = []
    for(let v of arr) {
        if(v < midValue)
            left.push(v)
        else
            right.unshift(v)
    }
    return quickSort(left).concat(midValue, quickSort(right))
}

console.log(quickSort(arr))

public class D {
    public static void main(String[] args) {
        int[] arr = {8, 4, 3, 7, 5, 1, 6, 9, 2};

        int iterCount = 0, swapCount = 0, lowCursor = 0, highCursor = arr.length - 1;
        boolean flag;

        while (lowCursor < highCursor) {
            flag = false;
            for (int i = lowCursor; i < highCursor; ++i) {
                iterCount++;
                if (arr[i] > arr[i + 1]) {
                    swapCount++;
                    flag = true;
                    arr[i] = arr[i] ^ arr[i + 1];
                    arr[i + 1] = arr[i] ^ arr[i + 1];
                    arr[i] = arr[i] ^ arr[i + 1];
                }
            }
            highCursor--;
            for (int i = highCursor; i > lowCursor; --i) {
                iterCount++;
                if (arr[i - 1] > arr[i]) {
                    swapCount++;
                    flag = true;
                    arr[i] = arr[i] + arr[i - 1];
                    arr[i - 1] = arr[i] - arr[i - 1];
                    arr[i] = arr[i] - arr[i - 1];
                }
            }
            lowCursor++;
            if (!flag) break;
        }

        for (int i = 0; i < arr.length; ++i)
            System.out.print(arr[i] + "\t");
        System.out.println();
        System.out.printf("iterCount: %d\n", iterCount);
        System.out.printf("swapCount: %d\n", swapCount);
    }
}