Worst Case Time Complexity: O(n^2)
const quickSort = (arr, low, high) => {
if (low >= 0 && high >= 0 && low < high) {
const partition = getPartition(arr, low, high);
quickSort(arr, low, partition);
quickSort(arr, partition + 1, high);
}
};
const getPartition = (arr, low, high) => {
const pivot = arr[low + Math.floor((high - low) / 2)];
let start = low - 1;
let end = high + 1;
while (true) {
do {
start++;
} while (arr[start] < pivot)
do {
end--;
} while (arr[end] > pivot)
if (start >= end) {
return end;
}
const temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
}
const arr = [4, 3, -1, 4, 1, 0];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // [-1, 0, 1, 3, 4, 4]