Implementation:Google deepmind Mujoco Engine Sort
| Knowledge Sources | |
|---|---|
| Domains | Physics Simulation, Sorting Algorithms |
| Last Updated | 2026-02-15 04:00 GMT |
Overview
Header-only implementation of generic sorting algorithms via C preprocessor macros, providing stable merge sort (timsort-style) and partial heap sort for MuJoCo's engine.
Description
This header defines two macro-based sorting facilities that generate type-safe, inline sorting functions. The mjSORT macro produces a stable timsort-style merge sort: it first applies insertion sort on small runs of size 32 (_mjRUNSIZE), then iteratively merges adjacent sorted runs with doubling merge length. The generated function signature is void name(type* arr, type* buf, int n, void* context) where buf is a scratch buffer of size n. The mjPARTIAL_SORT macro generates a partial sorting function that selects the bottom k elements using a max-heap, then sorts them with insertion sort. Helper sub-macros include _mjINSERTION_SORT for small-array sorting, _mjMERGE for merging two sorted subarrays, and _mjSIFT_DOWN for heap maintenance. All macros accept a user-defined comparison function and opaque context pointer, enabling flexible sorting criteria.
Usage
Used throughout the engine to define specialized sort functions for specific element types (contacts, constraints, etc.) at compile time, avoiding the overhead of function pointer-based generic sorting.
Code Reference
Source Location
- Repository: Google_deepmind_Mujoco
- File: src/engine/engine_sort.h
- Lines: 1-111
Key Functions
// Run size threshold for insertion sort
#define _mjRUNSIZE 32
// Insertion sort sub-macro
#define _mjINSERTION_SORT(type, arr, start, end, cmp, context)
// Merge sub-macro for two sorted subarrays
#define _mjMERGE(type, src, dest, start, mid, end, cmp, context)
// Timsort-style stable merge sort generator
// Generates: void name(type* arr, type* buf, int n, void* context)
#define mjSORT(name, type, cmp)
// Heap sift-down sub-macro
#define _mjSIFT_DOWN(type, buf, start, end, cmp, context)
// Partial heap sort generator (select bottom k elements)
// Generates: void name(type* arr, type* buf, int n, int k, void* context)
#define mjPARTIAL_SORT(name, type, cmp)
Import
#include "engine/engine_sort.h"
I/O Contract
Inputs
| Name | Type | Required | Description |
|---|---|---|---|
| arr | type* | Yes | Array to sort in-place |
| buf | type* | Yes | Scratch buffer of same size as arr |
| n | int | Yes | Number of elements in arr |
| k | int | Yes (partial sort) | Number of bottom elements to select |
| context | void* | No | Opaque context pointer passed to comparison function |
| cmp | function | Yes (macro arg) | Comparison function: int cmp(const type*, const type*, void* ctx) |
Outputs
| Name | Type | Description |
|---|---|---|
| arr | type* | Sorted array (in-place), or first k elements sorted for partial sort |