I'm wondering what is the time and space complexity of this quick sort implementation in JavaScript. Does it have more than the ideal time and space complexity of quick sort or is it same? (Ideal quick sort has TC O(n^2) and SC O(log n) in worst case)

function quickSort(arr)
{
    if(arr.length == 1)
        return arr
    
    let pivot = arr[arr.length-1];
    let left = [], right= [];

    for(let i=0; i<arr.length-1; i  )
        arr[i] <= pivot ? left.push(arr[i]) : right.push(arr[i]);

    if(left.length && right.length)
        return [...quickSort(left), pivot, ...quickSort(right)]
    else if(left.length)
        return [...quickSort(left), pivot]
    else
        return [pivot, ...quickSort(right)];
}

I'm assuming that it has more time and space complexity than the ideal quick sort implemantation.

CodePudding user response：

The worst case time complexity is also O(n²), for instance when the input is already sorted.

The auxiliary space complexity is O(nlogn).