Stable marriage (Gale–Shapley): Examples & Code

Algorithm Visualizations November 16, 2026 javascript

Published by Dimitris Kougioumtzis · Updated

Proposers make offers in preference order; receivers retain their preferred offer. Complete strict lists produce a proposer-optimal stable matching.

Proposers advance through preferences while receivers retain their best proposal so far; each pair is considered at most once.

Open the 3D visualization

Stable marriage (Gale–Shapley) example state preview
Preview of the example's final state. Complete values are available in the worked example and interactive timeline.

When to use Stable marriage (Gale–Shapley)

Stable two-sided allocation with strict complete preferences.

Choosing an alternative

Maximum-weight assignment optimizes utility, not the absence of blocking pairs.

Worked example: input and state changes

Example input

0,1,2;1,0,2;1,2,0 | 1,0,2;0,1,2;0,1,2

These checkpoints follow the actual example timeline. State details show the stored values and decisions; use the visualization to inspect every intervening step.

  1. Step 0: All participants begin unmatched.

    State at this checkpoint
    {
      "values": [
        "free",
        "free",
        "free",
        "free",
        "free",
        "free"
      ],
      "active": [],
      "kind": "graph",
      "bipartite": true,
      "nodeLabels": [
        "P0",
        "P1",
        "P2",
        "R0",
        "R1",
        "R2"
      ],
      "chosen": [],
      "visited": [],
      "partners": [
        -1,
        -1,
        -1
      ]
    }
  2. Step 2: R0 retains P0.

    State at this checkpoint
    {
      "values": [
        "R0",
        "free",
        "free",
        "P0",
        "free",
        "free"
      ],
      "active": [
        0,
        3
      ],
      "kind": "graph",
      "bipartite": true,
      "nodeLabels": [
        "P0",
        "P1",
        "P2",
        "R0",
        "R1",
        "R2"
      ],
      "chosen": [
        0
      ],
      "visited": [
        0,
        3
      ],
      "partners": [
        0,
        -1,
        -1
      ]
    }
  3. Step 5: Proposer P2 offers to R1.

    State at this checkpoint
    {
      "values": [
        "R0",
        "R1",
        "free",
        "P0",
        "P1",
        "free"
      ],
      "active": [
        2,
        4
      ],
      "kind": "graph",
      "bipartite": true,
      "nodeLabels": [
        "P0",
        "P1",
        "P2",
        "R0",
        "R1",
        "R2"
      ],
      "chosen": [
        0,
        1
      ],
      "visited": [
        0,
        3,
        1,
        4
      ],
      "partners": [
        0,
        1,
        -1
      ]
    }
  4. Step 7: Proposer P2 offers to R2.

    State at this checkpoint
    {
      "values": [
        "R0",
        "R1",
        "free",
        "P0",
        "P1",
        "free"
      ],
      "active": [
        2,
        5
      ],
      "kind": "graph",
      "bipartite": true,
      "nodeLabels": [
        "P0",
        "P1",
        "P2",
        "R0",
        "R1",
        "R2"
      ],
      "chosen": [
        0,
        1
      ],
      "visited": [
        0,
        3,
        1,
        4
      ],
      "partners": [
        0,
        1,
        -1
      ]
    }
  5. Step 9: Stable proposer-optimal matching complete.

    State at this checkpoint
    {
      "values": [
        "R0",
        "R1",
        "R2",
        "P0",
        "P1",
        "P2"
      ],
      "active": [],
      "kind": "graph",
      "bipartite": true,
      "nodeLabels": [
        "P0",
        "P1",
        "P2",
        "R0",
        "R1",
        "R2"
      ],
      "chosen": [
        0,
        1,
        2
      ],
      "visited": [
        0,
        3,
        1,
        4,
        2,
        5
      ],
      "partners": [
        0,
        1,
        2
      ]
    }

Expected final state

Stable proposer-optimal matching complete.

Complexity and input bounds

Family: Greedy. Time complexity: O(n²).

Space complexity: O(n squared) preference ranks plus O(n) matching state.

Working-space bounds describe algorithm state and any explicitly noted output, excluding the visualization's saved timeline. Recording frames can use more memory than running the function alone. Here n is sequence length, V and E are vertex and edge counts, and other parameters refer to the named input dimensions.

Proposer preference rows | receiver preference rows. Rows separated by semicolons; 1–5 participants per side, each row a permutation of 0..n-1.

The playground validates these limits before starting. Downloaded functions are callable implementations, with parameter and output-buffer contracts in their comments; they do not all repeat the playground's input validation.

Common mistakes and limitations

Stability does not mean maximum total happiness; the result favors the proposing side among stable matchings.

Further reading

For background on algorithm analysis and the JavaScript function interface:

Editorial and testing approach · Browse all algorithm guides

Complete JavaScript implementation

javascript
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 1–5 participants per side. Both arrays contain n row-major permutations of 0..n-1 with strict complete preferences. Writes proposer-to-receiver partners and returns n. Reference snippets assume validated playground inputs. Fixed scratch buffers have 256 slots. Sorting variants may use a different traversal strategy than the animation.
function algorithm(proposers, receivers, n, output) {
    let ranks = Array(256).fill(0); let matched = Array(256).fill(0); let next = Array(256).fill(0); let queue = Array(256).fill(0);
    for (let w = 0; w < n; w++) {
        matched[w] = -1; output[w] = -1; queue[w] = w;
        for (let i = 0; i < n; i++) { ranks[w * n + receivers[w * n + i]] = i; }
    }
    let head = 0; let tail = n;
    while (head < tail) {
        let m = queue[head++]; let w = proposers[m * n + next[m]++]; let old = matched[w];
        if (old < 0 || ranks[w * n + m] < ranks[w * n + old]) {
            matched[w] = m; output[m] = w;
            if (old >= 0) { output[old] = -1; queue[tail++] = old; }
        } else { queue[tail++] = m; }
    }
    return n;
}

Source

Primary research source for the algorithm or its underlying method. The playground is a bounded teaching implementation, not the publication's original program.