15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
A stable sorting algorithm keeps records with equal keys in their original relative order. If (2,A) comes before (2,B) in the input, it still does in the output. Stability is a promise on top of the sorting contract, which only needs nondecreasing keys and exactly the same records as the input.
| Sorting contract | Keys nondecreasing, and the output holds exactly the input records |
|---|---|
| Stable | Equal keys keep their input order; sorted plus a permutation does not imply it |
| Stable as taught here | Bubble, insertion and merge sort (left value wins ties), counting sort (right-to-left placement) |
| Not stable in basic form | Selection sort, quick sort, heap sort (long-distance swaps) |
| In place | O(1) auxiliary space; copying n values into a temporary array is O(n) |
| Checker cost | O(n^2) time, O(n) extra space for the used array |
A sorting contract needs a chosen order. Here, keys must be mutually comparable under that order. For ascending order, every pair of neighboring output keys must satisfy:
for every valid index , from 0 through length(a) - 2.
A correct sorting result has two required parts:
For records such as (2,A), the key is 2 and the tag A identifies the record. Sorting compares keys, but permutation preservation moves whole records. A result must not lose, duplicate, or invent records.
The lesson builds a checker for a candidate output. It does not perform sorting. It answers: “Is this candidate a nondecreasing permutation of this input?”
The checker does not mutate either array. It uses a separate used array to record which input records have already matched output records.
Source scope: Elementary Sorts.
Use tagged records so equal keys remain distinguishable.
| Index | 0 | 1 | 2 |
|---|---|---|---|
| Input record | (2,A) | (1,X) | (2,B) |
The input is:
1[(2,A), (1,X), (2,B)]A correct ascending output has key sequence [1,2,2]:
1[(1,X), (2,A), (2,B)]It has the same three records as the input. Its neighboring keys are:
11 <= 2
22 <= 2Now compare this other candidate:
1[(1,X), (2,B), (2,A)]It is also sorted and is also a permutation of the input. It changes the order of the equal-key records: B now appears before A.
That difference is called stability.
A sorting procedure is stable when records with equal keys keep their original relative order. The first output is stable because (2,A) appeared before (2,B) in the input and remains before it in the output. The second output is a valid sorting output, but it is not stable.
Start with the stable candidate:
1input = [(2,A), (1,X), (2,B)]
2candidate = [(1,X), (2,A), (2,B)]The checker has two jobs.
Check adjacent candidate keys.
| Adjacent indices | Keys compared | Result |
|---|---|---|
0, 1 | 1 <= 2 | true |
1, 2 | 2 <= 2 | true |
The candidate is nondecreasing.
Make one Boolean entry per input record.
| Input index | 0 | 1 | 2 |
|---|---|---|---|
| Input record | (2,A) | (1,X) | (2,B) |
used | false | false | false |
used[j] = true means input record j has already been matched to one candidate record. It cannot be matched again.
(1,X)Scan input records from index 0.
| Input index checked | Input record | Already used? | Same record as (1,X)? |
|---|---|---|---|
| 0 | (2,A) | false | no |
| 1 | (1,X) | false | yes |
Set used[1] to true.
| Input index | 0 | 1 | 2 |
|---|---|---|---|
used | false | true | false |
(2,A)Start again at input index 0.
| Input index checked | Input record | Already used? | Same record as (2,A)? |
|---|---|---|---|
| 0 | (2,A) | false | yes |
Set used[0] to true.
| Input index | 0 | 1 | 2 |
|---|---|---|---|
used | true | true | false |
(2,B)Scan from input index 0.
| Input index checked | Input record | Already used? | Action |
|---|---|---|---|
| 0 | (2,A) | true | skip |
| 1 | (1,X) | true | skip |
| 2 | (2,B) | false | match |
Set used[2] to true.
| Input index | 0 | 1 | 2 |
|---|---|---|---|
used | true | true | true |
Every candidate record matched one distinct input record. The candidate is a permutation.
The same checker accepts the unstable candidate because stability is outside the basic sorting contract:
1[(1,X), (2,B), (2,A)]It is ordered and preserves all records. Requiring stability needs an explicit promise from the sorting procedure and a trace that verifies equal-key records keep input order.
While matching candidate records, keep this fact true:
After matching candidate indices
0throughi - 1, each of those candidate records has been matched to one distinct input record, andused[j]is true exactly for the input records already matched.
The statement is the matching invariant.
At the beginning, no candidate records have been processed. Every used entry is false. The statement is true.
When the checker finds an unused identical input record for candidate record i, it marks exactly that input position as used. The new candidate record now has one match. Earlier matches remain distinct because the checker never reuses an entry whose used value is true.
If the checker reaches the end of the input without finding a match, then the candidate contains a record not available in the remaining input multiset. It cannot be a permutation.
At completion, every candidate record has a distinct input match. Since the arrays have equal lengths, all input records have also been matched exactly once.
The full sorting contract combines this matching fact with the earlier adjacent-order check:
Write down the decisions in the order they must happen.
false.false.used, with one false value for each input position.false.true.The order check compares keys. The permutation check compares whole records. For untagged arrays of numbers, a whole record is simply the number itself.
The checker returns a Boolean. It does not reorder input or candidate.
1FUNCTION IsNondecreasingPermutation(input, candidate) RETURNS Boolean
2 INPUT:
3 input: array of records
4 candidate: array of records
5 RETURN:
6 true exactly when candidate is nondecreasing by key
7 and contains the same records as input with the same multiplicities
8 MUTATION:
9 does not modify input or candidate
10 allocates and modifies a separate used array
11 PRECONDITION:
12 every record has a key, and all keys are mutually comparable
13 under the chosen ascending order
14
15 IF length(input) != length(candidate) THEN
16 RETURN false
17 END IF
18
19 n <- length(input)
20
21 // Check candidate[0..n-1] is nondecreasing by key.
22 FOR i <- 0 TO n - 2 DO
23 IF Key(candidate[i]) > Key(candidate[i + 1]) THEN
24 RETURN false
25 END IF
26 END FOR
27
28 used <- new array of n Boolean values, all false
29
30 // Match each candidate record to one unused identical input record.
31 FOR i <- 0 TO n - 1 DO
32 foundMatch <- false
33
34 FOR j <- 0 TO n - 1 DO
35 IF NOT used[j] AND SameRecord(input[j], candidate[i]) THEN
36 used[j] <- true
37 foundMatch <- true
38 BREAK
39 END IF
40 END FOR
41
42 IF NOT foundMatch THEN
43 RETURN false
44 END IF
45 END FOR
46
47 RETURN true
48END FUNCTIONHelper contracts:
1FUNCTION Key(record) RETURNS comparable key
2 Returns the key used for ascending-order comparisons.
3 Does not modify record.
4END FUNCTION
5
6FUNCTION SameRecord(left, right) RETURNS Boolean
7 Returns true exactly when left and right are the same full record.
8 For tagged records, both key and tag must match.
9 For bare values, the values must match.
10 Does not modify either record.
11END FUNCTIONFor n = 0, the order loop has no valid indices and the matching loop has no iterations. The function returns true, so [] is a nondecreasing permutation of [].
Use the original input and stable candidate.
1input = [(2,A), (1,X), (2,B)]
2candidate = [(1,X), (2,A), (2,B)]1length(input) = 3
2length(candidate) = 3The lengths match, so do not return false.
1n = 3i = 0
1Key(candidate[0]) = 1
2Key(candidate[1]) = 2
31 > 2 is falseContinue.
i = 1
1Key(candidate[1]) = 2
2Key(candidate[2]) = 2
32 > 2 is falseThe loop ends because i has reached n - 2 = 1. The candidate is nondecreasing.
used1used = [false, false, false]Outer-loop iteration: i = 0
1candidate[0] = (1,X)
2foundMatch = falseInner-loop iteration: j = 0
1used[0] = false
2SameRecord((2,A), (1,X)) = falseNo match. Continue.
Inner-loop iteration: j = 1
1used[1] = false
2SameRecord((1,X), (1,X)) = trueMatch found.
1used = [false, true, false]
2foundMatch = trueBreak out of the inner loop. Since foundMatch is true, do not return false.
Outer-loop iteration: i = 1
1candidate[1] = (2,A)
2foundMatch = falseInner-loop iteration: j = 0
1used[0] = false
2SameRecord((2,A), (2,A)) = trueMatch found.
1used = [true, true, false]
2foundMatch = trueBreak. Do not return false.
Outer-loop iteration: i = 2
1candidate[2] = (2,B)
2foundMatch = falseInner-loop iteration: j = 0
1used[0] = trueThe condition NOT used[0] is false. Skip this already matched record.
Inner-loop iteration: j = 1
1used[1] = trueSkip again.
Inner-loop iteration: j = 2
1used[2] = false
2SameRecord((2,B), (2,B)) = trueMatch found.
1used = [true, true, true]
2foundMatch = trueThe outer loop ends. The function reaches:
1RETURN trueThe stable candidate satisfies order and permutation preservation.
Assume the keys satisfy the precondition: they are mutually comparable under the selected ascending order.
The first loop examines every adjacent candidate pair:
1candidate[i], candidate[i + 1]for every valid i from 0 through n - 2.
If it finds Key(candidate[i]) > Key(candidate[i + 1]), the candidate is not nondecreasing, so returning false is correct.
If the loop finishes, every adjacent pair satisfies:
Therefore, the candidate is nondecreasing.
Before the matching loop begins, used contains only false. No candidate record has been processed, and no input record has been matched. The matching invariant holds.
At one outer-loop iteration, the algorithm processes candidate[i].
candidate[i], it marks that one input position as used.candidate[i] one match.used[j] = true.Each successful iteration preserves the matching invariant.
If an iteration cannot find an unused identical input record, then the candidate asks for a record that the unmatched input positions do not contain. The candidate is not a permutation, so returning false is correct.
If the loop terminates normally, all n candidate records have distinct input matches. The arrays have equal length, so those matches use all n input records exactly once. The candidate is a permutation of the input.
The algorithm returns true only after both the order loop and matching loop finish. Therefore, it returns true exactly when the candidate is a nondecreasing permutation of the input.
The proof does not establish stability because the checker does not test it. Stability requires an extra contract and a trace of equal-key record identities.
Let n be the common array length after the length check.
The order loop checks neighboring keys:
1i = 0 through n - 2That is exactly:
key comparisons when n >= 1.
The matching phase has an outer loop with n candidate records. For each one, the inner loop can inspect up to n input positions.
On an input that passes the checker but places each needed match late in the input scan, the matching work can reach:
record checks.
The order comparisons add n - 1, so the total shown work is:
in the quadratic case. The worst-case running time is .
The checker can stop earlier:
Its best case can be constant work when the lengths differ. Its average-case bound depends on how inputs and candidates are distributed; no single average-case claim follows without such a model.
For sorting procedures, best-case, average-case, and worst-case bounds may differ because different input families can produce different numbers of key comparisons and data movements. Count comparisons and writes or swaps separately for the particular sorting procedure being analyzed.
The checker allocates:
1used = [false, false, ..., false]with n Boolean entries.
That is auxiliary space beyond the two input arrays. It does not mutate either input array.
The checker is not in-place under the usual auxiliary-space convention. An implementation that copies n values into a separate output or temporary array also uses auxiliary space, even if it later overwrites the original array.
Incorrect assumption:
1"If candidate is sorted, return true."Small input that exposes it:
1input = [1,1,2]
2candidate = [1,2,2]The candidate is nondecreasing:
11 <= 2 <= 2But it lost one 1 and added an extra 2. It is not a permutation.
Correction: after checking order, match every candidate element to one distinct input element, or use another method that verifies equal multiplicities.
Incorrect assumption:
1"Swapping equal keys cannot matter."Small input that exposes it:
1input = [(2,A), (2,B)]
2output = [(2,B), (2,A)]The key sequence is still [2,2], so the output is sorted and is a permutation. But B moved ahead of A.
Correction: when stability is promised, track record identities such as tags. Equal keys must retain the order in which their full records appeared in the input.
Incorrect assumption:
1"Copy input into output[n], sort output, so the sort is in-place."Input that exposes the storage cost:
1[3,1,2]If the implementation allocates an array that can hold all n values, it uses storage proportional to n beyond the input:
1output = [_, _, _]For general input size n, this is auxiliary space.
Correction: report explicit temporary arrays as auxiliary space. State whether the original array is reordered or a separate result array is returned.
| Input | Correct sorted result or checker behavior |
|---|---|
[] | Returns []; the checker accepts [] as a permutation of []. |
[7] | Remains [7]. |
[2,2,2] | Is sorted; tags are needed to observe stability. |
[-1,0,-3] | Sorts to [-3,-1,0]. |
Executable objective: Given an input array and candidate output array, implement a checker that returns true exactly when the candidate is a nondecreasing permutation of the input. Tests include duplicates, negatives, and empty arrays.
Your checker will be tested against this contract:
[] paired with [];1
2def key(r):
3 return r[0]
4
5def is_nondecreasing_permutation(inp, cand):
6 if len(inp) != len(cand):
7 return False
8 n = len(inp)
9 for i in range(n - 1):
10 if key(cand[i]) > key(cand[i + 1]):
11 return False
12 used = [False] * n
13 for c in cand:
14 found = False
15 for j in range(n):
16 if not used[j] and inp[j] == c: # same key and same tag
17 used[j] = True
18 found = True
19 break
20 if not found:
21 return False
22 return True
23
24def is_stable(inp, cand):
25 # for every key, the tags must appear in the same order as in the input
26 for k in {key(r) for r in inp}:
27 if [r for r in inp if key(r) == k] != [r for r in cand if key(r) == k]:
28 return False
29 return True
30
31records = [(2, "A"), (1, "X"), (2, "B")]
32candidates = [
33 ("stable candidate", [(1, "X"), (2, "A"), (2, "B")]),
34 ("swapped candidate", [(1, "X"), (2, "B"), (2, "A")]),
35 ("lost a record", [(1, "X"), (2, "A"), (2, "A")]),
36]
37for name, cand in candidates:
38 ok = str(is_nondecreasing_permutation(records, cand)).lower()
39 st = str(is_stable(records, cand)).lower()
40 print(f"{name}: sorted permutation={ok}, stable={st}")1
2import java.util.*;
3
4public class Main {
5 static boolean sortedPermutation(int[][] in, int[][] cand) {
6 if (in.length != cand.length) return false;
7 int n = in.length;
8 for (int i = 0; i + 1 < n; i++) {
9 if (cand[i][0] > cand[i + 1][0]) return false;
10 }
11 boolean[] used = new boolean[n];
12 for (int[] c : cand) {
13 boolean found = false;
14 for (int j = 0; j < n && !found; j++) {
15 if (!used[j] && Arrays.equals(in[j], c)) { // same key and same tag
16 used[j] = true;
17 found = true;
18 }
19 }
20 if (!found) return false;
21 }
22 return true;
23 }
24
25 static boolean stable(int[][] in, int[][] cand) {
26 for (int[] r : in) {
27 List<Integer> before = new ArrayList<>(), after = new ArrayList<>();
28 for (int[] x : in) if (x[0] == r[0]) before.add(x[1]);
29 for (int[] x : cand) if (x[0] == r[0]) after.add(x[1]);
30 if (!before.equals(after)) return false; // equal keys changed order
31 }
32 return true;
33 }
34
35 public static void main(String[] args) {
36 int[][] records = {{2, 'A'}, {1, 'X'}, {2, 'B'}};
37 String[] names = {"stable candidate", "swapped candidate", "lost a record"};
38 int[][][] cands = {
39 {{1, 'X'}, {2, 'A'}, {2, 'B'}},
40 {{1, 'X'}, {2, 'B'}, {2, 'A'}},
41 {{1, 'X'}, {2, 'A'}, {2, 'A'}},
42 };
43 for (int i = 0; i < cands.length; i++) {
44 System.out.println(names[i] + ": sorted permutation=" + sortedPermutation(records, cands[i])
45 + ", stable=" + stable(records, cands[i]));
46 }
47 }
48}1
2#include <iostream>
3#include <string>
4#include <utility>
5#include <vector>
6using namespace std;
7
8using Rec = pair<int, char>; // (key, tag)
9
10bool sortedPermutation(const vector<Rec>& in, const vector<Rec>& cand) {
11 if (in.size() != cand.size()) return false;
12 size_t n = in.size();
13 for (size_t i = 0; i + 1 < n; i++) {
14 if (cand[i].first > cand[i + 1].first) return false;
15 }
16 vector<bool> used(n, false);
17 for (const Rec& c : cand) {
18 bool found = false;
19 for (size_t j = 0; j < n && !found; j++) {
20 if (!used[j] && in[j] == c) { // same key and same tag
21 used[j] = true;
22 found = true;
23 }
24 }
25 if (!found) return false;
26 }
27 return true;
28}
29
30bool isStable(const vector<Rec>& in, const vector<Rec>& cand) {
31 for (const Rec& r : in) {
32 string before, after;
33 for (const Rec& x : in) if (x.first == r.first) before += x.second;
34 for (const Rec& x : cand) if (x.first == r.first) after += x.second;
35 if (before != after) return false; // equal keys changed order
36 }
37 return true;
38}
39
40int main() {
41 vector<Rec> records = {{2, 'A'}, {1, 'X'}, {2, 'B'}};
42 vector<string> names = {"stable candidate", "swapped candidate", "lost a record"};
43 vector<vector<Rec>> cands = {
44 {{1, 'X'}, {2, 'A'}, {2, 'B'}},
45 {{1, 'X'}, {2, 'B'}, {2, 'A'}},
46 {{1, 'X'}, {2, 'A'}, {2, 'A'}},
47 };
48 cout << boolalpha;
49 for (size_t i = 0; i < cands.size(); i++) {
50 cout << names[i] << ": sorted permutation=" << sortedPermutation(records, cands[i])
51 << ", stable=" << isStable(records, cands[i]) << endl;
52 }
53}1
2const same = (a, b) => a[0] === b[0] && a[1] === b[1];
3
4function sortedPermutation(input, cand) {
5 if (input.length !== cand.length) return false;
6 const n = input.length;
7 for (let i = 0; i + 1 < n; i++) {
8 if (cand[i][0] > cand[i + 1][0]) return false;
9 }
10 const used = new Array(n).fill(false);
11 for (const c of cand) {
12 let found = false;
13 for (let j = 0; j < n && !found; j++) {
14 if (!used[j] && same(input[j], c)) { // same key and same tag
15 used[j] = true;
16 found = true;
17 }
18 }
19 if (!found) return false;
20 }
21 return true;
22}
23
24function isStable(input, cand) {
25 for (const [k] of input) {
26 const tags = (list) => list.filter((r) => r[0] === k).map((r) => r[1]).join('');
27 if (tags(input) !== tags(cand)) return false; // equal keys changed order
28 }
29 return true;
30}
31
32const records = [[2, 'A'], [1, 'X'], [2, 'B']];
33const candidates = [
34 ['stable candidate', [[1, 'X'], [2, 'A'], [2, 'B']]],
35 ['swapped candidate', [[1, 'X'], [2, 'B'], [2, 'A']]],
36 ['lost a record', [[1, 'X'], [2, 'A'], [2, 'A']]],
37];
38for (const [name, cand] of candidates) {
39 console.log(`${name}: sorted permutation=${sortedPermutation(records, cand)}, stable=${isStable(records, cand)}`);
40}Insertion sort, bubble sort, merge sort and counting sort are stable as written in these lessons. Each has a rule that protects equal keys: shift or swap only on strictly greater, take the left value on ties, or place right to left.
Stable, as long as the merge uses A[i] <= A[j] and so takes the left value on equal keys. Using < sends the right value first on ties and reverses equal records.
Unstable in its basic in-place form. Swaps in the partition step move equal keys past each other. With a last-element pivot, [(2,A), (2,B), (1,X)] ends as (1,X), (2,B), (2,A).
No. It swaps the minimum across the array. On [(2,A), (2,B), (1,X)] the first swap puts (2,A) behind (2,B), and nothing restores the order.
It lets you sort by one key and then another. Sort by name, then stably by grade, and students with equal grades stay in name order. LSD radix sort depends on stable digit passes for the same reason.
The sort rearranges the array with a constant number of extra variables. Copying n values into a temporary array costs O(n) auxiliary space, so that sort is not in place. Merge sort, with its auxiliary array, is the standard example.