Array Timsort

1.0.3 · maintenance · verified Sun Apr 19

The `array-timsort` package provides a JavaScript implementation of Python's highly optimized Timsort algorithm for stable array sorting. It is currently at version 1.0.3, with an apparent maintenance-only release cadence based on its last commit over two years ago. Unlike the `timsort` package it was forked from, `array-timsort` returns an array representing the original indices of elements after sorting, rather than `undefined`. Timsort is an adaptive, stable sorting algorithm that leverages existing order in data, achieving O(n) performance on partially sorted arrays and O(n log n) worst-case time complexity, with O(n) memory usage. Benchmarks suggest it can significantly outperform `Array.prototype.sort()` in Node.js for specific data distributions, such as descending arrays or those with many duplicates, while potentially being slower on certain random distributions.

Common errors

```
ReferenceError: require is not defined
```
cause Attempting to use `require()` in an ES module (`"type": "module"` in `package.json`) environment without proper setup.

fix Either convert your project to use ES modules exclusively, configure your build process to transpile/bundle CJS modules, or use dynamic `import()` within an async context if you must load CJS.
```
TypeError: (0 , array_timsort_1.sort) is not a function
```
cause Incorrect ES module import syntax being used for a CommonJS package. This typically occurs in TypeScript or ESM-aware environments when trying `import { sort } from 'array-timsort';` and the module isn't correctly resolved as CJS.

fix For TypeScript/ESM, ensure your `tsconfig.json` (`moduleResolution`) and build setup correctly handle CommonJS interop. Alternatively, use `import * as Timsort from 'array-timsort'; const { sort } = Timsort;` or revert to `const { sort } = require('array-timsort');` in a CJS context.

Warnings

gotcha Unlike the original `timsort` package it forks, `array-timsort` returns an array of original indices after sorting (e.g., `[2, 1, 0, 4]` for `[1, 2, 3, 5]`), while `timsort` returns `undefined`. This changes the expected return value for many users.
Fix: Adjust logic to handle the returned index mapping, or if in-place modification and `undefined` return is desired, consider using the original `timsort` package.
gotcha Performance is highly dependent on data distribution and array size. Benchmarks indicate that `array-timsort` can be slower than native `Array.prototype.sort()` for certain types of random arrays (e.g., lengths 100, 1000) in specific Node.js versions, despite being significantly faster on others.
Fix: Benchmark with your specific data sets and array sizes to determine if `array-timsort` offers a performance benefit for your use case.
gotcha The package is designed for CommonJS environments and uses `require()`. Direct ES module `import` statements (e.g., `import { sort } from 'array-timsort'`) may fail in pure ESM contexts or build tools without explicit CJS interoperability.
Fix: Use `const { sort } = require('array-timsort')` for Node.js projects, or configure your bundler (e.g., Webpack, Rollup) to handle CJS modules in an ESM project.

Install

npm install array-timsort npm
yarn add array-timsort yarn
pnpm add array-timsort pnpm

Imports

sort (named destructuring)
wrong:
```
import { sort } from 'array-timsort'
```
correct:
```
const { sort } = require('array-timsort')
```
The 'sort' function is exported as a named property from the CommonJS module. Direct ES module 'import' is not natively supported and will likely fail in pure ESM environments.
sort (property access)
wrong:
```
const sort = require('array-timsort');
sort(array);
```
correct:
```
const timsortModule = require('array-timsort');
timsortModule.sort(array);
```
The `require('array-timsort')` call returns the module object, not the `sort` function directly. Access the function via `timsortModule.sort`.
sort (incorrect path)
wrong:
```
const sort = require('array-timsort/index').sort;
```
correct:
```
const { sort } = require('array-timsort')
```
The correct and idiomatic way to import is directly from the package name. Do not try to import from sub-paths like '/index' unless explicitly documented.

Quickstart

Demonstrates basic array sorting with a custom comparator, in-place modification, and sorting a specific subrange, highlighting the returned index map.

const { sort } = require('array-timsort');

// Example 1: Sorting a basic numerical array in ascending order
// The Timsort algorithm is adaptive and stable, making it efficient
// for partially sorted data while maintaining element order for equal values.
const numbers = [30, 10, 20, 5, 15, 25, 40, 35, 45, 0];
console.log('Original numbers:', numbers.slice()); // Log a copy to show original state

// Define a numerical comparison function
function numberCompare(a, b) {
    return a - b;
}

// Perform the sort using the custom comparator
// The `sort` function modifies the array in-place and returns
// an array of original indices mapping to their new positions.
const originalIndicesMap = sort(numbers, numberCompare);

console.log('Sorted numbers:', numbers);
console.log('Original indices map:', originalIndicesMap);

// Example 2: Sorting a specific subrange of an array
const mixedArray = ['apple', 'zebra', 'banana', 'grape', 'fig', 'date', 'elderberry'];
console.log('\nOriginal mixed array:', mixedArray.slice());

// Sort elements from index 2 ('banana') up to (but not including) index 6 ('elderberry') alphabetically
sort(mixedArray, 2, 6); 

console.log('Mixed array with subrange sorted:', mixedArray);

view raw JSON →