Кстати если хочеться очень-очень быстро сортировать строки советую взглянуть на Burstsort у него O(wn), где w - это максимальная длина строки в массиве

Отсюда вывод: нужно больше value-типов! 😄

@maxgraey кстати, смотрел заметку про Machine Learned sort? Весьма умно и круто. 😊

По стандарту в ECMAScript стабильная для всего, но раньшне этого небыло) Поэтому и был выбран тот алгоритм, чейчас все на TimSort перелезли, но я считаю это ошибкой. В общем там у меня алгоритм на основке merge sort но значительно быстрее

нет, еще нет

сортировка вставками... но все равно посмотри, мб ошибка где

const N = 10000
const stringArray = new Array<string>(N)
const i32Array = new Array<i32>(N)

export function getstringArrayLength(): i32 {
  return stringArray.length
}
export function sInit(): void {
  for(let i = 0; i < N; i++)
    stringArray[i] = ( Math.random().toString() )
}
export function sSort(): void {
  stringArray.sort((l, r) => l < r ? -1 : 1)
}

export function i32Init(): void {
  for(let i = 0; i < N; i++)
    i32Array[i] = i32( Math.random() * 1e9 )
}
export function i32Sort(): void {
  i32Array.sort((l, r) => l - r)
}

Рекомендую. Там не сильно много и не сложно, если в детали не закапываться.

врятли другой алгоритм может в 3к раз медленнее работать

const N = 10000
const stringArray = new Array<string>(N)
const i32Array = new Array<i32>(N)

export function getstringArrayLength(): i32 {
  return stringArray.length
}
export function sInit(): void {
  for(let i = 0; i < N; i++)
    stringArray[i] = ( Math.random().toString() )
}
export function sSort(): void {
  stringArray.sort((l, r) => l < r ? -1 : 1)
}

export function i32Init(): void {
  for(let i = 0; i < N; i++)
    i32Array[i] = i32( Math.random() * 1e9 )
}
export function i32Sort(): void {
  i32Array.sort((l, r) => l - r)
}

Нет здесь никакой ошибки. Для строк сейчас происходит фолбек на сортировку вставками у которой O(N^2) в наихудем случае. Для интов weap haep sort у которого
O(N log N).

insertionSort (strings): 10000 ** 2   =>      100000000
weakHeap (ints): 10000 * log2(10000)   =>  132877

100000000 / 132877 = 750

Это если очень грубо, не учитывая амортизацию

то есть в 750 раз. Кроме того учитывай что сравнение двух строк значительно медленее сравнения двух интов. Вот и получаем 3000x и это еще не предел

Еще раз советую пока взглянуть на Burstsort если нужно сортировать именно строк)

Понятно, спс

такая либа уже есть в ас?

Нет, либы под AS нету. Но можно портировать скажем из этой реализации:
https://github.com/MirzaAribaBaig/BurstSort/blob/master/burstsort/Program.cs

Кстати, там есть и MultikeyQuickSort который стоит использовать в случае если не извесен заранее алфавит (то есть нужен весь диапазон юникода)

Но он там используется как вспомогательный алгоритм

ок

Ты про это? https://arxiv.org/pdf/1805.04272.pdf

Нет, я про этот: https://blog.acolyer.org/2020/10/19/the-case-for-a-learned-sorting-algorithm/ 😊

> Learned Sort outperforms the next best competitor, RadixSort, by a factor of 1.49x.

Для того что бы обогнать RadixSort много ума не нужно) Достаточно взять хорошо реализованный counting sort. Так как у него
O(n + k)
а у radix sort:
O(w * n)