🌙 @moon7/sort

A lightweight, functional utility library providing composable sorting functions for arrays and collections in JavaScript and TypeScript applications.

✨ Features

• 🧱 Basic Comparators - Ascending, descending, and random sorting functions
• 🏷️ Property-based Sorting - Sort by specific object properties
• 🧩 Composable API - Combine multiple sort criteria effortlessly
• 🧶 Natural Sorting - Intelligent string sorting with proper handling of numbers
• ⛓️ Chaining - Order, group, and prioritize items with composable functions

📦 Installation

1# Using npm
2npm install @moon7/sort
3
4# Using yarn
5yarn add @moon7/sort
6
7# Using pnpm
8pnpm add @moon7/sort

🧠 Motivation

Sorting functions in JavaScript compare two values and return a numeric result: negative (-1) when the first value is less than the second, positive (1) when greater, and zero (0) when they're equal.

1// A sorting function's type signature
2type Comparator<T> = (a: T, b: T) => number;
3
4// Common imperative sorting pattern
5numberList.sort((a, b) => a - b);

While simple cases are straightforward, complex sorting logic can quickly become unwieldy when written imperatively. This library takes a functional approach, providing composable building blocks that you can combine to create sophisticated sorting behaviors with minimal code.

1import { ascending, descending } from "@moon7/sort";
2
3// Simple sorting using ascending/descending comparators
4list.sort(ascending);
5
6// How it works:
7// const ascending: Comparator<T> = (a, b) => a === b ? 0 : a < b ? -1 : 1;
8// const descending: Comparator<T> = (a, b) => a === b ? 0 : a < b ? 1 : -1;

Most functions in this library are higher-order functions - they accept other functions as arguments and return new functions, enabling powerful composition patterns.

1import { by, descending, naturally, flip } from "@moon7/sort";
2
3// Sort by name, ascending (ascending is default)
4list.sort(by(x => x.name));
5
6// Sort by name, descending
7list.sort(by(x => x.name, descending));
8
9// Sort by name, using natural string sorting
10list.sort(by(x => x.name, naturally));
11
12// Sort by name, using natural string sorting, descending
13list.sort(by(x => x.name, flip(naturally)));
14
15// How it works:
16// `by` takes a mapping function and an optional comparator, returning a new comparator
17// const by = (map, cmp: Comparator<T> = ascending): Comparator<T> => (a, b) => cmp(map(a), map(b));

Here's an example where you can combine multiple sorting criteria. Notice how this reads like a clear declaration of your sorting requirements.

1import { by, order, naturally, descending } from "@moon7/sort";
2
3// Sort by name naturally, then by age descending, then by lastLogin
4list.sort(
5    order(
6        by(x => x.name, naturally),
7        by(x => x.age, descending),
8        by(x => x.lastLogin),
9    )
10);
11
12// How it works:
13// `order` takes multiple comparators and returns a new comparator that applies them in sequence

Traditional imperative approach would require nested if statements or complex logic. With functional composition, we can express the sorting intent declaratively.

🚀 Usage

🧱 Basic Sorting

1import { ascending, descending, preserve, dir, Direction, random, randomly } from '@moon7/sort';
2
3// Sort an array in ascending order
4const numbers = [3, 1, 4, 2];
5numbers.sort(ascending);
6// [1, 2, 3, 4]
7
8// Sort in descending order
9numbers.sort(descending);
10// [4, 3, 2, 1]
11
12// Sort using a direction enum
13numbers.sort(dir(Direction.Ascending));  // ascending
14numbers.sort(dir(Direction.Descending)); // descending
15
16// Sort using any truthy values
17numbers.sort(dir(true)); // ascending
18numbers.sort(dir(0)); // descending
19
20// Sort in random order
21// Note: this has bias, not for statistical applications
22numbers.sort(random(0.5));
23
24// Same as above, with default probability threshold
25numbers.sort(randomly);
26
27// Sort using the identity function, which retains existing order
28numbers.sort(preserve);
29
30// Sort using the inverse identity function, which reverses the array
31numbers.sort(reverse);

⚠️ Note: The random() and randomly functions produce biased results and are not suitable for statistical or cryptographic applications. For proper random shuffling, use the Fisher-Yates algorithm instead.

The preserve comparator always returns 1, which maintains the original order when used with JavaScript's Array.sort(). It serves as an identity function for comparators - useful when working with higher-order functions that require a comparator parameter, but you want to maintain the original order.

The reverse comparator always returns -1, which reverses the original order when used with Array.sort(). This provides a simple way to reverse an array without changing its relative ordering logic otherwise.

⚠️ Note on Stability: The preserve and reverse comparators require a stable sorting algorithm to work correctly. Before ES2019, JavaScript's native Array.prototype.sort() wasn't guaranteed to be stable, with behavior varying across engines. For consistent results:

• Use an ES2019+ environment where stable sorting is guaranteed
• Or use this library's sort() function, which automatically detects and uses your engine's stable sort implementation or falls back to our stable timSort() implementation
• Or directly use timSort() or mergeSort(), which is always stable regardless of environment

Check out the practical examples in the Advanced Sorting section below to see these in action.

🔍 Sorting Objects by Properties

1import { by, order, descending } from '@moon7/sort';
2
3const people = [
4    { name: 'Alice', age: 30 },
5    { name: 'Bob', age: 25 },
6    { name: 'Charlie', age: 30 }
7];
8
9// Sort by age (ascending by default)
10people.sort(by(p => p.age));
11// [
12//     { name: 'Bob', age: 25 },
13//     { name: 'Alice', age: 30 },
14//     { name: 'Charlie', age: 30 }
15// ]
16
17// Sort by age descending
18people.sort(by(p => p.age, descending));
19
20// Sort by age, then by name descending
21people.sort(order(
22    by(p => p.age),
23    by(p => p.name, descending)
24));
25// [
26//     { name: 'Bob', age: 25 },
27//     { name: 'Charlie', age: 30 },
28//     { name: 'Alice', age: 30 }
29// ]

📊 Natural Sorting

1import { natural, naturally, by, Sensitivity } from '@moon7/sort';
2
3const versions = ['v1.10', 'v1.2', 'v1.1'];
4
5// Sort with natural comparison (1.2 comes before 1.10)
6versions.sort(natural());
7// ['v1.1', 'v1.2', 'v1.10']
8
9// Using pre-configured naturally constant (same as natural() with default settings)
10versions.sort(naturally);
11// ['v1.1', 'v1.2', 'v1.10']
12
13// Sort strings differently based on their case sensitivity
14const names = ['alice', 'Alice', 'bob', 'Bob'];
15names.sort(natural(Sensitivity.Case));
16// ['alice', 'Alice', 'bob', 'Bob']
17
18// Sort objects with string properties using natural sort
19const files = [
20    { name: 'file10.txt' },
21    { name: 'file2.txt' }
22];
23files.sort(by(f => f.name, naturally));
24// [
25//     { name: 'file2.txt' },
26//     { name: 'file10.txt' }
27// ]

⛓️ Advanced Sorting

1import { where, nullable, group, flip, conditional, preserve } from '@moon7/sort';
2
3// Sort active items first, then by name
4const items = [
5    { name: 'Task 1', active: false },
6    { name: 'Task 2', active: true },
7    { name: 'Task 3', active: false },
8    { name: 'Task 4', active: true },
9];
10items.sort(where(x => x.active, by(x => x.name)));
11// [
12//     { name: 'Task 2', active: true },
13//     { name: 'Task 4', active: true },
14//     { name: 'Task 1', active: false },
15//     { name: 'Task 3', active: false },
16// ]
17
18// Preserve original order when sorting
19const nums = [3, 1, 4, 2];
20nums.sort(preserve);
21// [3, 1, 4, 2] (unchanged)
22
23// Reverse original order when sorting
24nums.sort(reverse);
25// [2, 4, 1, 3] (reversed)
26
27// Group by category, but preserve original order within each group
28const categoryItems = [
29    { id: 1, category: 'A' },
30    { id: 2, category: 'B' },
31    { id: 3, category: 'A' },
32];
33categoryItems.sort(group(item => item.category, ascending, preserve));
34// [
35//     { id: 1, category: 'A' },
36//     { id: 3, category: 'A' },
37//     { id: 2, category: 'B' },
38// ]
39
40// Sort with null values first
41const products = [
42    { name: 'Product A', price: 10 },
43    { name: 'Product B', price: null }
44];
45products.sort(nullable(p => p.price));
46// [
47//     { name: 'Product B', price: null },
48//     { name: 'Product A', price: 10 }
49// ]
50
51// Group items by status, then sort by date within groups
52const tasks = [
53    { status: 'pending', created: new Date(2023, 1, 1) },
54    { status: 'active', created: new Date(2023, 2, 1) },
55    { status: 'active', created: new Date(2023, 1, 15) }
56];
57tasks.sort(group(
58    x => x.status,
59    // active at the top, archived at the bottom
60    by(status => ['active', 'pending', 'archived'].indexOf(status)),
61    // within each group, sort by created
62    by(x => x.created)
63));
64// [
65//     { status: 'active', created: new Date(2023, 1, 15) },
66//     { status: 'active', created: new Date(2023, 2, 1) },
67//     { status: 'pending', created: new Date(2023, 1, 1) }
68// ]
69
70// Conditional sorting
71const numbers = [-5, -2, 3, 1];
72numbers.sort(conditional(
73  (a, b) => a < 0 && b < 0,  // If both numbers are negative
74  descending,                // Sort negative numbers in descending order
75  ascending                  // Sort other numbers in ascending order
76));
77// [-2, -5, 1, 3]

🧮 Sorting Algorithms

This library provides three main sorting functions, each with different characteristics to suit various use cases:

sort(arr, cmp?)

The recommended general-purpose sorting function that sorts arrays in-place. It intelligently selects the best available stable sorting implementation:

1import { sort } from '@moon7/sort';
2
3// Sort an array using the optimal stable sorting algorithm
4const sorted = sort([3, 1, 4, 2]);

• In-place Operation: Modifies and sorts the original array directly
• Algorithm Selection: Uses the native Array.prototype.sort() if your JavaScript environment has a stable implementation (ES2019+), otherwise falls back to mergeSort
• Stability: Always stable, meaning equal elements maintain their relative order
• Use Cases: Best default choice when you need deterministic behavior across all environments

mergeSort(arr, cmp?, small?)

A stable, in-place implementation of the merge sort algorithm:

1import { mergeSort } from '@moon7/sort';
2
3// Sort directly with mergeSort
4const sorted = mergeSort([3, 1, 4, 2]);

• Algorithm: Hybrid merge sort with insertion sort for small subarrays
• Performance: O(n log n) time complexity with consistent performance regardless of input distribution
• Stability: Always stable (equal elements maintain their relative order)
• Small Array Optimization: The small parameter defines the subarray size threshold below which the algorithm switches to insertion sort for better performance
• Memory Usage: O(n) auxiliary space in the worst case
• Use Cases: When stability is essential, or when sorting nearly-sorted or reversed arrays

quickSort(arr, cmp?, small?)

An optimized, in-place implementation of the quicksort algorithm:

1import { quickSort } from '@moon7/sort';
2
3// Sort directly with quickSort
4const sorted = quickSort([3, 1, 4, 2]);

• Algorithm: Three-way partitioning quicksort with median-of-three pivot selection and insertion sort for small subarrays
• Performance: O(n log n) average time complexity, potentially O(n²) in worst case (but rare due to optimizations)
• Stability: Not stable (equal elements may change their relative order)
• Memory Usage: O(log n) auxiliary space for recursion in average case
• Small Array Optimization: The small parameter defines the subarray size threshold below which the algorithm switches to insertion sort for better performance
• Best For: Random data, arrays with duplicates, and moderately sized arrays
• Not Ideal For: Fully reversed arrays or when stability is required

According to benchmarks, quickSort outperforms the other sorting functions in most scenarios, except when dealing with fully reversed data where mergeSort or native sort is faster. Run pnpm benchmarks to see benchmarks.

timSort(arr, cmp?)

A hybrid sorting algorithm based on the implementation used in Python, Java, and other programming languages:

1import { timSort } from '@moon7/sort';
2
3// Sort directly with timSort
4const sorted = timSort([3, 1, 4, 2]);

• Algorithm: Hybrid algorithm combining merge sort and insertion sort, optimized for real-world data
• Performance: O(n log n) time complexity with adaptive optimizations for partially sorted data
• Stability: Always stable (equal elements maintain their relative order)
• Memory Usage: O(n) auxiliary space
• Best For: Real-world data with partially sorted subarrays or "runs"
• Key Features: Natural run detection, galloping mode for efficiently merging runs with large differences, and small array optimization

TimSort excels at handling real-world data that often contains partially-ordered sections. It's particularly efficient for sorting large datasets with pre-existing order patterns.

📚 API Reference

The library provides these key functions:

API	Description
🧮 Sorting Functions
sort(arr, cmp?)	In-place stable sort (native or mergeSort fallback)
mergeSort(arr, cmp?, small?)	Stable in-place sort with optimization for small arrays
quickSort(arr, cmp?, small?)	Fast in-place sort, not stable but generally more efficient
timSort(arr, cmp?)	Hybrid stable sort with optimal performance for real-world data
nativeSort(arr, cmp?)	Same as Array.prototype.sort()
insertionSort(arr, cmp?)	Stable, in-place sort efficient for small or nearly sorted arrays
insertionRangeSort(arr, lo, hi, cmp?)	Insertion sort for a specific range within an array
🧰 Utility Functions
isNativeSortStable()	Checks if native sort is stable, and caches result
🏷️ Enums
Direction.Ascending	Enum value representing ascending sort order
Direction.Descending	Enum value representing descending sort order
Sensitivity.Base	Enum value for different bases unequal, cases/accents equal
Sensitivity.Accent	Enum value for accents/bases unequal, cases equal
Sensitivity.Case	Enum value for cases/bases unequal, accents equal
Sensitivity.Variant	Enum value for all variations considered unequal
🧱 Basic Comparators
ascending	Compares values in ascending order
descending	Compares values in descending order
preserve	Identity comparator that preserves original order
reverse	Comparator that reverses the original order
dir(isAscending)	Creates a comparator for a specific direction
🎲 Shuffle Comparators
random(p)	Creates a comparator that sorts randomly with given probability
randomly	Pre-configured random sort comparator with p=0.5
🧶 String Comparators
natural(sensitivity?)	Creates a comparator for natural string sorting
naturally	Pre-configured natural sort comparator with default settings
🧩 Complex Comparators
by(map, cmp?)	Creates a comparator based on a property or derived value
order(...fns)	Combines multiple comparators in sequence
where(predicate, cmp?)	Creates a comparator that prioritizes items matching a predicate
nullable(get, cmp?)	Creates a comparator that prioritizes null/undefined values
group(selector, groupOrder?, itemOrder?)	Groups items and orders both groups and items within groups
conditional(condition, ifTrue, ifFalse)	Selects between comparators based on a condition
flip(fn, ignore?)	Flips the result of another comparator

Note that all comparators are functions in the form of (a, b) => number, which is omitted in the table above for brevity. For example, ascending is actually a function ascending(a, b).

Likewise, by(map, cmp?) is a function by(map, cmp?)(a, b), as it is a higher-order comparator. Any parameter that expects a comparator can accept these functions directly.

🔗 Related Libraries

Library	Description	npm
@moon7/async	Asynchronous utilities for promises, semaphores, and concurrent operations
@moon7/bits	Bit manipulation utilities and binary operations
@moon7/inspect	Runtime type checking with powerful, composable type inspectors
@moon7/result	Functional error handling with Result and Maybe types
@moon7/signals	Reactive programming with Signals, Sources, and Streams

🤝 Contributing

We welcome contributions from everyone! See our contributing guide for more details on how to get involved. Please feel free to submit a Pull Request.

📝 License

This project is licensed under the MIT License - see the LICENSE file for details.

🌟 Acknowledgements

Created and maintained by Munir Hussin.

The mergeSort algorithm (source code) is ported from Haxe.

This library evolved from moon-core's Compare.