Массивы «Быстрая сортировка» (Хоара)

O(log₂n*n)
самый быстрый

разделяй и властвуй

делим массив на подмассивы и каждый раз рекурсивно
мы выбираем опорный элемент у каждого массива
его можно выбрать случайно, но часто центрально
пробегаемся по массиву и все элементы, которые меньше опорного, добавляем в один массив, все которые больше, добавляем в другой массив.
После такой операции у нас получается два массива
(с меньшими числами и с большими числами чем опорные).

Для каждого из этих массивов выполняется точно такая же операция. В каждой из этих массивов выбирается опорный элемент и происходит сортировка и так происходит до тех пор, пока длина массива становится равна единице (именно это условие и будет базовым случаем выхода из рекурсии).

И после этих операций эти маленькие массивы склеиваются в один большой.

const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;

function quickSort(arr){
 if (arr.length<=1){
  return arr
}
let pivotIndex = Math.floor(arr.length/2);
let pivot=arr[pivotIndex]
let less=[]
let greater=[]

for(let i=0;i<arr.length;i++){
 cnt+=1
 if(i===pivotIndex)
  continue;
 if(arr[i]<pivot){
  less.push(arr[i])
} else {
 greater.push(arr[i])
}
return [...quickSort(less),pivot,...quickSort(greater)]
}

console.log(quickSort(arr))
console.log(cnt);