Блочная (карманная, корзинная) сортировка / Bucket sort Блочная сортировка - это алгоритм, основанный на разделении входного массива на несколько частей - блоки/сегменты - и использовании другого алгоритма для их сортировки.
Общая идея алгоритма:
Пример реализации на Kotlin: fun insertion_sort(arr: ArrayList) {
var n = arr.size
var i: Int
for (j in 1 until n) {
var key = arr[j]
i = j - 1
while (i >= 0 && arr[i] > key) {
arr[i + 1] = arr[i]
i--
}
arr[i + 1] = key
}
}
fun bucketSort(arr:Array) {
var n = arr.size
var bucket = Array>(n, {i-> ArrayList() } )