Пацаны, кто разбирается в MergeSort? Делим массив на две половины

(и сортируем их), через .sort ?
Что-то у меня медленнее на 10%, чем Array.prototype.sort

const shuffleArray = arr => {
const len = arr.length
for (let i = 0; i < len - 1; i += 1) {
let r = Math.floor(Math.random() * (len - i))
r && ([arr[i], arr[i + r]] = [arr[i + r], arr[i]])
}
return arr
}

const chaoticArray = shuffleArray(Array(20).fill(0).map((_, i) => i + 1))

const mergeSort = array => {
const pivot = (start, end) => Math.floor((start + end) / 2);
const len = array.length
let tempA = [...array]
let tempB = tempA.splice(pivot(0, len), len - 1)

tempA = tempA.sort((a, b) => a - b)
tempB = tempB.sort((a, b) => a - b)

let i = 0
let j = 0
let k = 0
const result = []

while (k < len) {
if (tempA[i] < tempB[j]) {
result.push(tempA[i])
i++
} else {
result.push(tempB[j])
j++
}
k++
}
return result;
}

Любой написаный тобой код будет медленнее чем Array.prototype.sort

От входных данных никак не будет зависеть?

А должно? Нативный метод на то и нативный что написан не на жс и не тобой

А написанный тобой?

Некрасиво пишешь, пойдем по разам выйдем

И написаный мной тоже

const shuffleArray = arr => { const len = arr.length for (let i = 0; i < len - 1; i += 1) { let r = Math.floor(Math.random() * (len - i)) r && ([arr[i], arr[i + r]] = [arr[i + r], arr[i]]) } return arr } const chaoticArray = shuffleArray(Array(20).fill(0).map((_, i) => i + 1)) const selectionSort = array => { for (let i = 0; i < array.length - 1; i += 1) { let min = i; for (let j = i + 1; j < array.length; j += 1) { if (array[min] > array[j]) min = j; } [array[i], array[min]] = [array[min], array[i]]; } return array } const mergeSort = array => { const pivot = (start, end) => Math.floor((start + end) / 2); const len = array.length let tempA = [...array] let tempB = tempA.splice(pivot(0, len), len) tempA = selectionSort(tempA) tempB = selectionSort(tempB) let i = 0 let j = 0 let k = 0 const result = [] while (k < len) { if (tempA[i] < tempB[j]) { result.push(tempA[i]) i += 1 } else { result.push(tempB[j]) j += 1 } k += 1 } return result; } console.log(mergeSort(chaoticArray))

Ну просто у алгоритмов сортировки есть best case и worst case в зависимости от порядка элементов в исходном массиве. Если подогнать худшие данные под quicksort, или что там сейчас под капотом нативно, и написать алгоритм который такой порядок сортирует быстрее, то нет ли шансов в этом случае победить?

Да, я думал о таком

Ну и чего? Быстрее нативного?

на 20 элементов быстрее нативный, на 200 быстрее мой, на 1000 быстрее нативный

Ну то есть не быстрее

На 200 элементах измерения не достоверны, особенно в жс

ситуативно

SelectionSort с вложенным циклом, можно другой алгоритм попробовать. у тебя есть в закладках какой-нибудь эффективный цикл сортировки?

на 20 000 нативный сорт на 90% быстрее, ладно короче нет смысла тягаться с V8 Torgue Timsort

Есть, мержсорт )