# Sorting

> In-place sorts with an explicit comparator.

```zig
const std = @import("std");
const expect = std.testing.expect;

const Person = struct {
    name: []const u8,
    age: u8,
};

fn byAge(_: void, a: Person, b: Person) bool {
    return a.age < b.age;
}

test "sort numbers" {
    var numbers = [_]u8{ 5, 3, 9, 1 };
    std.mem.sort(u8, &numbers, {}, std.sort.asc(u8));
    try expect(numbers[0] == 1 and numbers[3] == 9);

    std.mem.sort(u8, &numbers, {}, std.sort.desc(u8));
    try expect(numbers[0] == 9);
}

test "sort structs with a custom comparator" {
    var people = [_]Person{
        .{ .name = "c", .age = 30 },
        .{ .name = "a", .age = 10 },
        .{ .name = "b", .age = 20 },
    };
    // The `{}` is the context argument: a value passed to every comparison,
    // useful when the ordering depends on something external.
    std.mem.sort(Person, &people, {}, byAge);
    try expect(people[0].age == 10);
}

test "sort strings lexicographically" {
    var words = [_][]const u8{ "pear", "apple", "fig" };
    std.mem.sort([]const u8, &words, {}, struct {
        fn lessThan(_: void, a: []const u8, b: []const u8) bool {
            return std.mem.order(u8, a, b) == .lt;
        }
    }.lessThan);
    try expect(std.mem.eql(u8, words[0], "apple"));
}

test "binary search a sorted slice" {
    const sorted = [_]u8{ 1, 3, 5, 7, 9 };
    const index = std.sort.binarySearch(u8, &sorted, @as(u8, 7), struct {
        fn order(key: u8, item: u8) std.math.Order {
            return std.math.order(key, item);
        }
    }.order);
    try expect(index.? == 3);
}

test "sort is not stable; sortUnstable is faster" {
    var numbers = [_]u8{ 4, 2, 6 };
    // `std.mem.sort` is stable. When equal elements are interchangeable,
    // `sortUnstable` avoids the extra work.
    std.mem.sortUnstable(u8, &numbers, {}, std.sort.asc(u8));
    try expect(numbers[0] == 2);
}
```

*Runnable: compiled to WebAssembly and executed by CI against Zig master. (`03-standard-library.sorting`)*

```zig
std.mem.sort(T, slice, context, lessThanFn);
```

For simple orderings the comparator is provided: `std.sort.asc(T)` and
`std.sort.desc(T)`.

## The context argument

That third parameter is passed to every comparison. It is `{}` (the void
value) when the ordering depends only on the elements. It becomes useful when
the comparison needs something external, such as sorting indices by the values
they point at:

```zig
std.mem.sort(usize, &indices, values, byReferencedValue);
```

That is what saves you from reaching for a global.

## Stable or not

| Function | Stable | Notes |
| --- | --- | --- |
| `std.mem.sort` | yes | equal elements keep their relative order |
| `std.mem.sortUnstable` | no | less work; prefer when elements are interchangeable |

Stability matters when you sort by one key and want a previous sort by another
key preserved within ties.

## Comparators as anonymous structs

Zig has no closures, so a one-off comparator is usually written as a struct
literal with a function in it:

```zig
std.mem.sort([]const u8, &words, {}, struct {
    fn lessThan(_: void, a: []const u8, b: []const u8) bool {
        return std.mem.order(u8, a, b) == .lt;
    }
}.lessThan);
```

`std.mem.order` returns `.lt` / `.eq` / `.gt`, which is also what
`std.sort.binarySearch` wants.