TimSort: Fast Sorting

An adaptive and stable sort algorithm based on merging that requires fewer than nlog(n) comparisons when run on partially sorted arrays. The algorithm uses O(n) memory and still runs in O(nlogn) (worst case) on random arrays.
This implementation is based on the original TimSort developed by Tim Peters for Python's lists.

Usage

import { sort } from "@dewars/timsort";

// Sort an array of numbers
const numbers = [5, 3, 2, 8, 7, 4, 1, 6];
sort(numbers);

// Sort an array of objects
const objects = [
  { name: "John", age: 25 },
  { name: "Jane", age: 22 },
  { name: "Alice", age: 27 },
];
sort(objects, (a, b) => a.age - b.age);

Performance

A benchmark is provided in that compares the timsort module against the default array.sort method in the numerical sorting of different types of integer array (as described here):

• Random array
• Descending array
• Ascending array
• Ascending array with 3 random exchanges
• Ascending array with 10 random numbers in the end
• Array of equal elements
• Random Array with many duplicates
• Random Array with some duplicates

Stability

TimSort is stable which means that equal items maintain their relative order after sorting. Stability is a desirable property for a sorting algorithm. Consider the following array of items with an height and a weight.

[
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 },
];

Items are already sorted by weight. Sorting the array according to the item's height with the timsort module results in the following array:

[
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 },
];