Нетривиальная сортировка: Шелла, быстрая, поразрядная

живой пример

import java.util.Arrays;

public class ShellDemo {
    public static void main(String[] args) {
        int[] a = {62, 83, 18, 53, 7, 17, 95, 86, 47, 69};
        int moves = 0, h = 1;
        while (h <= a.length / 3) h = h * 3 + 1;
        while (h > 0) {
            for (int i = h; i < a.length; i++) {
                int tmp = a[i], j = i;
                while (j >= h && a[j - h] > tmp) { a[j] = a[j - h]; j -= h; moves++; }
                a[j] = tmp;
            }
            System.out.println("h = " + h + ": " + Arrays.toString(a));
            h = (h - 1) / 3;
        }
        System.out.println("перемещений всего: " + moves);
    }
}

живой пример

package main

import "fmt"

func main() {
	a := []int{62, 83, 18, 53, 7, 17, 95, 86, 47, 69}
	moves, h := 0, 1
	for h <= len(a)/3 {
		h = h*3 + 1
	}
	for h > 0 {
		for i := h; i < len(a); i++ {
			tmp, j := a[i], i
			for j >= h && a[j-h] > tmp {
				a[j] = a[j-h]
				j -= h
				moves++
			}
			a[j] = tmp
		}
		fmt.Printf("h = %d: %v\n", h, a)
		h = (h - 1) / 3
	}
	fmt.Println("перемещений всего:", moves)
}

живой пример

const a = [62, 83, 18, 53, 7, 17, 95, 86, 47, 69];
let moves = 0;
let h = 1;
while (h <= Math.floor(a.length / 3)) h = h * 3 + 1;
while (h > 0) {
  for (let i = h; i < a.length; i++) {
    const tmp = a[i];
    let j = i;
    while (j >= h && a[j - h] > tmp) {
      a[j] = a[j - h];
      j -= h;
      moves++;
    }
    a[j] = tmp;
  }
  console.log(`h = ${h}: [${a.join(", ")}]`);
  h = Math.floor((h - 1) / 3);
}
console.log("перемещений всего:", moves);

живой пример

a = [62, 83, 18, 53, 7, 17, 95, 86, 47, 69]
moves, h = 0, 1
while h <= len(a) // 3:
    h = h * 3 + 1
while h > 0:
    for i in range(h, len(a)):
        tmp, j = a[i], i
        while j >= h and a[j - h] > tmp:
            a[j] = a[j - h]
            j -= h
            moves += 1
        a[j] = tmp
    print(f"h = {h}: {a}")
    h = (h - 1) // 3
print("перемещений всего:", moves)

живой пример

import java.util.Arrays;

public class QuickDemo {
    static int comparisons = 0;

    static void quickSort(int[] a, int left, int right) {
        if (right <= left) return;
        int p = partition(a, left, right);
        quickSort(a, left, p - 1);
        quickSort(a, p + 1, right);
    }

    static int partition(int[] a, int left, int right) {
        int pivot = a[right], i = left;
        for (int j = left; j < right; j++) {
            comparisons++;
            if (a[j] < pivot) swap(a, i++, j);
        }
        swap(a, i, right);
        return i;
    }

    static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

    public static void main(String[] args) {
        int[] mixed = {3, 8, 2, 7, 1, 6, 5, 4};
        quickSort(mixed, 0, 7);
        System.out.println("вперемешку: " + Arrays.toString(mixed) + ", сравнений " + comparisons);
        comparisons = 0;
        quickSort(new int[]{1, 2, 3, 4, 5, 6, 7, 8}, 0, 7);
        System.out.println("уже по возрастанию: сравнений " + comparisons);
    }
}

живой пример

package main

import "fmt"

var comparisons = 0

func quickSort(a []int, left, right int) {
	if right <= left {
		return
	}
	p := partition(a, left, right)
	quickSort(a, left, p-1)
	quickSort(a, p+1, right)
}

func partition(a []int, left, right int) int {
	pivot, i := a[right], left
	for j := left; j < right; j++ {
		comparisons++
		if a[j] < pivot {
			a[i], a[j] = a[j], a[i]
			i++
		}
	}
	a[i], a[right] = a[right], a[i]
	return i
}

func main() {
	mixed := []int{3, 8, 2, 7, 1, 6, 5, 4}
	quickSort(mixed, 0, 7)
	fmt.Printf("вперемешку: %v, сравнений %d\n", mixed, comparisons)
	comparisons = 0
	quickSort([]int{1, 2, 3, 4, 5, 6, 7, 8}, 0, 7)
	fmt.Println("уже по возрастанию: сравнений", comparisons)
}

живой пример

let comparisons = 0;

function quickSort(a, left, right) {
  if (right <= left) return;
  const p = partition(a, left, right);
  quickSort(a, left, p - 1);
  quickSort(a, p + 1, right);
}

function partition(a, left, right) {
  const pivot = a[right];
  let i = left;
  for (let j = left; j < right; j++) {
    comparisons++;
    if (a[j] < pivot) swap(a, i++, j);
  }
  swap(a, i, right);
  return i;
}

function swap(a, i, j) { [a[i], a[j]] = [a[j], a[i]]; }

const mixed = [3, 8, 2, 7, 1, 6, 5, 4];
quickSort(mixed, 0, 7);
console.log(`вперемешку: [${mixed.join(", ")}], сравнений ${comparisons}`);
comparisons = 0;
quickSort([1, 2, 3, 4, 5, 6, 7, 8], 0, 7);
console.log(`уже по возрастанию: сравнений ${comparisons}`);

живой пример

comparisons = 0


def quick_sort(a: list, left: int, right: int) -> None:
    if right <= left:
        return
    p = partition(a, left, right)
    quick_sort(a, left, p - 1)
    quick_sort(a, p + 1, right)


def partition(a: list, left: int, right: int) -> int:
    global comparisons
    pivot, i = a[right], left
    for j in range(left, right):
        comparisons += 1
        if a[j] < pivot:
            a[i], a[j] = a[j], a[i]
            i += 1
    a[i], a[right] = a[right], a[i]
    return i


mixed = [3, 8, 2, 7, 1, 6, 5, 4]
quick_sort(mixed, 0, 7)
print(f"вперемешку: {mixed}, сравнений {comparisons}")
comparisons = 0
quick_sort([1, 2, 3, 4, 5, 6, 7, 8], 0, 7)
print(f"уже по возрастанию: сравнений {comparisons}")

static void sort3(int[] a, int lo, int hi) {
    if (hi <= lo) return;
    int lt = lo, gt = hi, i = lo, p = a[lo];
    while (i <= gt) {
        if (a[i] < p) swap(a, lt++, i++);
        else if (a[i] > p) swap(a, i, gt--);
        else i++;
    }
    sort3(a, lo, lt - 1);
    sort3(a, gt + 1, hi);
}

func sort3(a []int, lo, hi int) {
	if hi <= lo {
		return
	}
	lt, gt, i, p := lo, hi, lo, a[lo]
	for i <= gt {
		switch {
		case a[i] < p:
			a[lt], a[i] = a[i], a[lt]
			lt++
			i++
		case a[i] > p:
			a[i], a[gt] = a[gt], a[i]
			gt--
		default:
			i++
		}
	}
	sort3(a, lo, lt-1)
	sort3(a, gt+1, hi)
}

function sort3(a, lo, hi) {
  if (hi <= lo) return;
  let lt = lo, gt = hi, i = lo;
  const p = a[lo];
  while (i <= gt) {
    if (a[i] < p) swap(a, lt++, i++);
    else if (a[i] > p) swap(a, i, gt--);
    else i++;
  }
  sort3(a, lo, lt - 1);
  sort3(a, gt + 1, hi);
}

def sort3(a: list, lo: int, hi: int) -> None:
    if hi <= lo:
        return
    lt, gt, i, p = lo, hi, lo, a[lo]
    while i <= gt:
        if a[i] < p:
            a[lt], a[i] = a[i], a[lt]
            lt += 1
            i += 1
        elif a[i] > p:
            a[i], a[gt] = a[gt], a[i]
            gt -= 1
        else:
            i += 1
    sort3(a, lo, lt - 1)
    sort3(a, gt + 1, hi)

Свою быструю сортировку в рабочем коде почти не пишут: Arrays.sort уже отлажена и учитывает вырожденные случаи лучше самодельной. Знать про неё нужно одно: под этим именем прячутся два разных алгоритма, и выбор идёт по типу данных.

Для примитивов (int[], long[], double[]) работает двухопорная быстрая сортировка (класс в JDK так и называется — DualPivotQuicksort). Это та же схема разбиения, что выше, только опорных элементов два и массив режется не на две части, а на три: меньше первого опорного, между опорными, больше второго. В среднем O(N·log N), лишней памяти почти не просит.

От вырождения в O(N²) есть страховка, появившаяся в Java 14 вместе с переписанным DualPivotQuicksort: если рекурсия уходит подозрительно глубоко — верный признак того, что опорные раз за разом неудачны, — библиотека переключается на пирамидальную сортировку с гарантированной O(N·log N). А самые короткие участки, как обычно, досортировываются вставками.

Для объектов (Arrays.sort(T[], Comparator), Collections.sort, list.sort(...)) работает TimSort: слияние плюс вставки. Он устойчив, ищет в данных уже упорядоченные куски и на почти готовых данных приближается к O(N). Расплата — память: ему нужен временный массив размером до половины исходного — вдвое экономнее классического слияния, с которого статья начиналась.

Разделение не случайное. У примитивов равные значения неразличимы, устойчивость там смысла не имеет — значит, можно взять более быструю и экономную по памяти быструю сортировку. У объектов два элемента с одинаковым ключом различаются всем остальным, и порядок между ними важен — поэтому там слияние, которое даёт устойчивость даром.

Есть ещё Arrays.parallelSort: та же идея, но куски сортируются в нескольких потоках и сливаются. Выигрыш — только на действительно больших массивах: на маленьких раздача работы съедает всё.

Грабля. Arrays.sort(int[]) не принимает компаратор: примитивы сортируются только по возрастанию, и никак иначе. Чтобы получить убывание, приходится заворачивать числа в объекты:

живой пример

import java.util.Arrays;
import java.util.Comparator;

public class ReverseDemo {
    public static void main(String[] args) {
        Integer[] ids = {5, 2, 9};
        Arrays.sort(ids, Comparator.reverseOrder());
        System.out.println(Arrays.toString(ids));
    }
}

И это уже совсем другая цена: вместо плотного массива чисел — массив ссылок на объекты, вместо быстрой сортировки — TimSort со своим временным массивом. На больших объёмах дешевле отсортировать int[] как есть и развернуть результат одним проходом.

Свою быструю сортировку в рабочем коде почти не пишут: slices.Sort уже отлажена и учитывает вырожденные случаи лучше самодельной. Знать про неё нужно одно: в отличие от Java, под этим именем один алгоритм для всех типов, и он не слияние.

Для всего, что сортируют slices.Sort, slices.SortFunc, sort.Ints и sort.Slice, с Go 1.19 работает pdqsort (pattern-defeating quicksort). Это та же схема разбиения, что выше, с тремя добавками: опорный выбирается медианой из нескольких элементов, уже упорядоченные и обратно упорядоченные куски распознаются и не пересортировываются, поэтому на готовых данных сортировка близка к O(N), а участки короче двенадцати элементов досортировываются вставками. В среднем O(N·log N), лишней памяти почти не просит.

От вырождения в O(N²) есть страховка: если разбиения раз за разом выходят неудачными — верный признак злонамеренного или очень неудачного входа, — библиотека переключается на пирамидальную сортировку с гарантированной O(N·log N). Отсюда и слово «pattern-defeating» в названии: алгоритм побеждает входы, которые ломали классическую быструю сортировку.

Расплата за скорость — неустойчивость: равные по ключу элементы могут поменяться местами. Для объектов, где порядок равных важен, есть slices.SortStableFunc и sort.Stable: внутри вставки блоками и слияние блоков на месте, устойчиво, без временного массива, но ценой лишних обменов: O(N·log N) сравнений и O(N·log² N) обменов. То есть выбор тот же, что в других языках, только делается он не по типу данных, а руками: неустойчиво и быстро по умолчанию, устойчиво по явной просьбе.

Параллельной сортировки в стандартной библиотеке нет: при необходимости срез режут на части по горутинам и сливают, как во внешней сортировке ниже.

Грабля. Срез это окно в общий массив, и slices.Sort переставляет элементы прямо в нём. Отсортировать кусок a[1:4] значит переставить элементы внутри a, а отсортированную копию можно получить только сделав копию: slices.Sorted(slices.Values(a)) с Go 1.23 или slices.Clone перед сортировкой. Убывание при этом дешёвое, никакой упаковки, как в Java, не нужно:

живой пример

package main

import (
	"cmp"
	"fmt"
	"slices"
)

func main() {
	a := []int{9, 5, 2, 7, 1}
	slices.Sort(a[1:4])
	fmt.Println("отсортировали кусок, а поменялся исходный:", a)

	ids := []int{5, 2, 9}
	slices.SortFunc(ids, func(x, y int) int { return cmp.Compare(y, x) })
	fmt.Println("по убыванию:", ids)
}

Первая строка показывает, что переставились именно элементы a с первого по третий. Вторая — что для убывания достаточно поменять местами аргументы в cmp.Compare; тот же результат даёт slices.Sort и затем slices.Reverse.

Свою быструю сортировку в рабочем коде почти не пишут: array.sort уже отлажена и учитывает вырожденные случаи лучше самодельной. Знать про неё нужно одно: в отличие от Java, под этим именем один алгоритм для всех данных, и это не быстрая сортировка.

Для обычных массивов в движке V8 с 2018 года работает TimSort: слияние плюс вставки. Он устойчив, и с ES2019 это требование стандарта, ищет в данных уже упорядоченные куски и на почти готовых данных приближается к O(N). Расплата — память: ему нужен временный массив размером до половины исходного. Быстрой сортировки с её экономией памяти для обычных массивов в языке нет, и выбрать её нельзя.

Разделение по типу данных всё же есть, но проходит оно по другой границе: у типизированных массивов (Int32Array, Float64Array) свой sort, который без функции сравнения сортирует числа как числа, а не как строки, и делает это заметно быстрее обычного массива: элементы лежат плотно, сравнивать их дёшево, а устойчивость для одинаковых чисел не наблюдаема. Для больших числовых данных это и есть аналог быстрой сортировки примитивов.

Параллельной сортировки нет: JavaScript однопоточный, а раздать работу воркерам через worker_threads с общим SharedArrayBuffer почти всегда дороже, чем отсортировать на месте.

Грабля. sort не возвращает новый массив, а переставляет элементы в исходном и возвращает его же. Строчка const sorted = items.sort(...) создаёт иллюзию копии, а на деле items уже отсортирован, и код, который полагался на исходный порядок, ломается далеко от места сортировки. Убывание при этом дешёвое, никакой упаковки, как в Java, не нужно:

живой пример

const ids = [5, 2, 9];
const desc = ids.sort((a, b) => b - a);
console.log("по убыванию:", desc, "исходный:", ids, "один и тот же массив:", desc === ids);
console.log("копия через toSorted:", [5, 2, 9].toSorted((a, b) => b - a));

Первая строка показывает, что desc и ids — один объект. Вторая — toSorted из ES2023 (Node 20), которая возвращает копию и исходный массив не трогает.

Свою быструю сортировку в рабочем коде почти не пишут: sorted уже отлажена и учитывает вырожденные случаи лучше самодельной. Знать про неё нужно одно: в отличие от Java, под этим именем один алгоритм для всех данных, и это не быстрая сортировка.

И sorted, и list.sort — это TimSort: слияние плюс вставки, придуманный для Python и потом перенятый Java и V8. Он устойчив, и это гарантия языка, ищет в данных уже упорядоченные куски и на почти готовых данных приближается к O(N). Расплата — память: ему нужен временный массив размером до половины исходного. Быстрой сортировки с её экономией памяти в стандартной библиотеке нет, и выбрать её нельзя; когда данных много и это числа, берут NumPy, у которого np.sort предлагает и быструю (по умолчанию, точнее introsort), и устойчивую, и поразрядную для целых.

Разделения по типу данных нет: числа и объекты идут через одну и ту же сортировку, разница только в цене сравнения. У чисел она мала, но каждое число всё равно отдельный объект, и это главная причина, почему сортировка миллиона чисел в Python в десятки раз медленнее, чем в Go или Java, и почему для чисел зовут NumPy.

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

Грабля. У list.sort() и sorted() разные возвращаемые значения: первая переставляет элементы на месте и возвращает None, вторая строит новый список. Строчка ids = ids.sort() тихо оставляет в ids пустоту. Убывание при этом дешёвое: параметр reverse=True, и никакой упаковки, как в Java, не нужно:

живой пример

ids = [5, 2, 9]
print("по убыванию, копия:", sorted(ids, reverse=True))
print("на месте, вернул:", ids.sort(reverse=True))
print("сам список:", ids)

Первая строка отсортированная копия, исходный список не тронут. Вторая печатает None: это и есть ловушка присваивания. Третья показывает, что ids при этом отсортирован. reverse=True сохраняет устойчивость: равные элементы остаются в исходном порядке, а не переворачиваются.

живой пример

import java.util.Arrays;

public class MergeSortDemo {
    static void mergeSort(int[] a) {
        if (a.length < 2) return;
        int[] left = Arrays.copyOfRange(a, 0, a.length / 2);
        int[] right = Arrays.copyOfRange(a, a.length / 2, a.length);
        mergeSort(left);
        mergeSort(right);
        merge(left, right, a);
    }

    static void merge(int[] left, int[] right, int[] out) {
        int i = 0, j = 0, k = 0;
        while (i < left.length && j < right.length) {
            out[k++] = left[i] <= right[j] ? left[i++] : right[j++];   // <= держит устойчивость
        }
        while (i < left.length) out[k++] = left[i++];
        while (j < right.length) out[k++] = right[j++];
    }

    public static void main(String[] args) {
        int[] a = {5, 2, 4, 6, 1, 3, 2};
        mergeSort(a);
        System.out.println(Arrays.toString(a));
    }
}

живой пример

package main

import "fmt"

func mergeSort(a []int) []int {
	if len(a) < 2 {
		return a
	}
	left := mergeSort(a[:len(a)/2])
	right := mergeSort(a[len(a)/2:])
	return merge(left, right)
}

func merge(left, right []int) []int {
	out := make([]int, 0, len(left)+len(right))
	i, j := 0, 0
	for i < len(left) && j < len(right) {
		if left[i] <= right[j] { // <= держит устойчивость
			out = append(out, left[i])
			i++
		} else {
			out = append(out, right[j])
			j++
		}
	}
	out = append(out, left[i:]...)
	return append(out, right[j:]...)
}

func main() {
	fmt.Println(mergeSort([]int{5, 2, 4, 6, 1, 3, 2}))
}

живой пример

function mergeSort(a) {
  if (a.length < 2) return a;
  const mid = Math.floor(a.length / 2);
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);   // <= держит устойчивость
  }
  return out.concat(left.slice(i), right.slice(j));
}

console.log(mergeSort([5, 2, 4, 6, 1, 3, 2]));

живой пример

def merge_sort(a):
    if len(a) < 2:
        return a
    mid = len(a) // 2
    return merge(merge_sort(a[:mid]), merge_sort(a[mid:]))


def merge(left, right):
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:      # <= держит устойчивость
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]


print(merge_sort([5, 2, 4, 6, 1, 3, 2]))

// набросок: Run читает свой временный файл, current — текущая запись
PriorityQueue<Run> heads = new PriorityQueue<>(Comparator.comparing(r -> r.current));
for (Run run : runs) if (run.advance()) heads.add(run);
while (!heads.isEmpty()) {
    Run r = heads.poll();
    out.write(r.current);
    if (r.advance()) heads.add(r);
}

// набросок: run читает свой временный файл, current — текущая запись,
// runHeap реализует heap.Interface и сравнивает по current
heads := &runHeap{}
for _, r := range runs {
	if r.advance() {
		heap.Push(heads, r)
	}
}
for heads.Len() > 0 {
	r := heap.Pop(heads).(*run)
	out.Write(r.current)
	if r.advance() {
		heap.Push(heads, r)
	}
}

// набросок: run читает свой временный файл, current — текущая запись,
// MinHeap — двоичная куча из статьи про кучи с функцией «меньше»
const heads = new MinHeap((a, b) => a.current < b.current);
for (const run of runs) if (run.advance()) heads.push(run);
while (heads.size > 0) {
  const r = heads.pop();
  out.write(r.current);
  if (r.advance()) heads.push(r);
}

В Python этот шаг уже написан: heapq.merge(*runs) лениво сливает отсортированные итераторы через ту же кучу. Набросок показывает, что у него внутри:

# набросок: run читает свой временный файл, current — текущая запись
heads = []
for run in runs:
    if run.advance():
        heapq.heappush(heads, (run.current, id(run), run))
while heads:
    _, _, r = heapq.heappop(heads)
    out.write(r.current)
    if r.advance():
        heapq.heappush(heads, (r.current, id(r), r))

List<int[]> merge(List<int[]> intervals) {
    intervals.sort(Comparator.comparingInt(a -> a[0]));
    List<int[]> out = new ArrayList<>();
    for (int[] cur : intervals) {
        int[] last = out.isEmpty() ? null : out.get(out.size() - 1);
        if (last != null && cur[0] <= last[1]) last[1] = Math.max(last[1], cur[1]);
        else out.add(new int[]{cur[0], cur[1]});
    }
    return out;
}

func merge(intervals [][2]int) [][2]int {
	slices.SortFunc(intervals, func(a, b [2]int) int { return cmp.Compare(a[0], b[0]) })
	var out [][2]int
	for _, cur := range intervals {
		if n := len(out); n > 0 && cur[0] <= out[n-1][1] {
			out[n-1][1] = max(out[n-1][1], cur[1])
		} else {
			out = append(out, cur)
		}
	}
	return out
}

function merge(intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  const out = [];
  for (const [start, end] of intervals) {
    const last = out.at(-1);
    if (last && start <= last[1]) last[1] = Math.max(last[1], end);
    else out.push([start, end]);
  }
  return out;
}

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda iv: iv[0])
    out: list[list[int]] = []
    for start, end in intervals:
        if out and start <= out[-1][1]:
            out[-1][1] = max(out[-1][1], end)
        else:
            out.append([start, end])
    return out

• В Java Arrays.sort — это два алгоритма: DualPivotQuicksort для примитивов (быстро, без устойчивости) и TimSort для объектов (устойчиво, ценой временного массива).

• В Go slices.Sort — это pdqsort для всего: быстро, без буфера, но неустойчиво, со страховкой пирамидальной сортировкой; устойчивость даёт slices.SortStableFunc ценой лишних обменов. Сортировка куска среза переставляет элементы исходного.

• В JavaScript sort — это TimSort для всего: устойчиво, ценой временного массива; быстрая сортировка недоступна, числовой аналог — sort типизированных массивов. sort меняет массив на месте, копию даёт toSorted.

• В Python sorted и list.sort — это TimSort для всего: устойчиво, ценой временного массива; быстрая сортировка недоступна, для чисел берут NumPy. list.sort() возвращает None, убывание даёт reverse=True.