Real-World Sorting in JavaScript and Python

How Real Programming Languages Sort

Understanding the sorting algorithms used by major programming languages helps you write more efficient code and predict performance characteristics.

JavaScript: V8's Timsort

Since 2019, V8 (Chrome, Node.js) uses Timsort for Array.prototype.sort(). Previously it used a combination of Quick Sort and Insertion Sort.

Key characteristics:

• Stable: Required by the ECMAScript specification since ES2019
• Time: O(n log n) worst case, O(n) on already-sorted arrays
• Space: O(n) for temporary merge buffer
• Threshold: Uses Insertion Sort for runs shorter than 32 elements

// JavaScript sort is stable and uses Timsort internally
const data = [
  { name: "Alice", age: 30 },
  { name: "Bob", age: 25 },
  { name: "Carol", age: 30 },
];
data.sort((a, b) => a.age - b.age);
// Alice(30) comes before Carol(30) — stable

Python: Timsort

Python's list.sort() and sorted() use Timsort, invented by Tim Peters in 2002 specifically for Python. It was later adopted by Java and JavaScript.

Key features:

• Identifies existing sorted runs in the data
• Extends short runs with Insertion Sort (minimum run length ~32-64)
• Merges runs using a galloping merge that is efficient for partially sorted data
• Uses a stack-based merge strategy with invariants to ensure efficiency

# Python's sort is stable and adaptive
data.sort(key=lambda x: x.department)
# Elements within the same department retain their previous order

Java: Dual-Pivot Quick Sort + Timsort

Java uses two different algorithms:

• Primitives (int[], double[]): Dual-pivot Quick Sort (unstable, but primitives don't need stability)
• Objects (Object[]): Timsort (stable, because equal objects might be distinguishable)

C/C++: Introsort

• std::sort: Introsort (Quick Sort + Heap Sort + Insertion Sort) — not guaranteed stable
• std::stable_sort: Merge Sort — stable, O(n log n), O(n) extra space

Writing Efficient Comparators

// BAD: String conversion is slow
arr.sort(); // Converts to strings first!

// GOOD: Numeric comparison
arr.sort((a, b) => a - b);

// GOOD: Multi-key sort
arr.sort((a, b) => a.dept.localeCompare(b.dept) || a.name.localeCompare(b.name));

Performance Tips

1. Avoid sorting when possible: If you only need the top k elements, use a partial sort or selection algorithm
2. Sort-friendly data layout: Arrays of primitives sort faster than arrays of objects due to cache locality
3. Presorted detection: Both Timsort and Introsort detect sorted input; avoid shuffling before sorting
4. Custom comparators: Keep comparators simple — they are called O(n log n) times