Formal Definition of Sorting - Sorting Problem Formalization & Stability | OneNoughtOne

0/361

Data Structures & AlgorithmsSorting Problem Formalization & Stability

Sorting Problem Formalization & Stability

LevelBeginner

Duration60 mins

TopicSorting Problem Formalization & Stability

1 / 4

Formal Definition of Sorting

What Does It Really Mean to Sort?

Sorting seems deceptively simple. Ask anyone to sort a list of numbers, and they'll intuitively arrange them from smallest to largest. But as software engineers, we must move beyond intuition. We need a precise, mathematical definition that captures exactly what sorting means—because that precision is what allows us to reason rigorously about correctness, design better algorithms, and handle edge cases that intuition misses.

Consider these questions that intuition struggles to answer definitively:

Is the sorted version of [3, 3, 3] just [3, 3, 3]? How do we prove it?
If two elements are "equal," does it matter which comes first?
What does "sorted" mean for objects that aren't numbers—dates, strings, custom records?
Can we define sorting for any data type, or only for those with a natural ordering?

The formal definition of sorting answers all of these questions unambiguously.

Learning Objectives

By the end of this page, you will understand the formal mathematical definition of sorting, the concept of total orderings, the relationship between permutations and sorting, and the key properties that any correct sorting algorithm must satisfy.

The Intuitive Foundation

Before diving into formal definitions, let's establish what sorting means intuitively. When we sort a collection of items, we're rearranging them so that they follow a specific order—typically from "smallest" to "largest" or vice versa.

The everyday experience of sorting:

Alphabetizing a list of names: Alice, Bob, Charlie, David...
Organizing files by date: oldest first or newest first
Ranking scores: highest to lowest for leaderboards
Arranging playing cards: by suit and value

In each case, we're taking an unordered (or arbitrarily ordered) collection and producing an ordered one according to some criterion. But notice something subtle: we're not just producing any ordered collection—we're rearranging the exact same elements we started with.

Key Insight: Sorting Is Rearrangement

Sorting doesn't create new elements or remove existing ones. It takes the exact input elements and outputs a rearranged version where the elements follow a specified ordering. This rearrangement is mathematically called a permutation.

This seemingly obvious point has profound implications:

The input and output have identical contents — Every element in the input appears exactly once in the output, and vice versa.
The output satisfies an ordering constraint — Each consecutive pair of elements obeys the ordering relationship.
The output is deterministic — For a given input and ordering, there may be multiple valid sorted outputs (when elements are equal), but all must satisfy the same constraints.

With this intuition established, we're ready to formalize these ideas mathematically.

Total Ordering — The Mathematical Foundation

To define sorting precisely, we first need to understand what it means for elements to be "comparable" and "orderable." This requires the concept of a total ordering from mathematics.

Definition: Total Ordering (Linear Ordering)

A total ordering on a set S is a binary relation ≤ (read as "less than or equal to") that satisfies the following four properties for all elements a, b, c in S:

Properties of a Total Ordering

•Reflexivity — Every element is related to itself: a ≤ a for all a. An element is always "less than or equal to" itself.
•Antisymmetry — If a ≤ b and b ≤ a, then a = b. Two different elements cannot both be less than or equal to each other.
•Transitivity — If a ≤ b and b ≤ c, then a ≤ c. The ordering "chains" logically across elements.
•Totality (Comparability) — For any two elements, either a ≤ b or b ≤ a (or both). Every pair of elements is comparable.

Why Total Ordering Matters for Sorting:

The totality property is what makes sorting possible. If we couldn't compare every pair of elements, we couldn't determine their relative positions in a sorted sequence.

Examples of Total Orderings:

Common Total Orderings in Programming
Domain	Ordering Relation	Example Comparisons
Integers	Standard ≤	3 ≤ 5, -1 ≤ 0, 7 ≤ 7
Real numbers	Standard ≤	3.14 ≤ 3.15, -2.5 ≤ 0.0
Characters	ASCII/Unicode order	'A' < 'B' < 'a' < 'b'
Strings	Lexicographic order	"apple" < "banana" < "cherry"
Dates	Chronological order	Jan 1 < Feb 15 < Dec 31
Booleans	false < true	false < true (0 < 1)

Partial Orderings Cannot Be Sorted

Some relations are partial orderings where not all pairs are comparable. For example, the subset relation (⊆) on sets: {1} and {2} are incomparable (neither is a subset of the other). You cannot sort items with only a partial ordering without first defining a tiebreaker to make it total.

Permutations — The Language of Rearrangement

When we sort a sequence, we're rearranging its elements—mathematically, we're applying a permutation.

Definition: Permutation

A permutation of a sequence is a rearrangement of all its elements into a new sequence, where every original element appears exactly once.

For a sequence of n elements, there are exactly n! (n factorial) possible permutations:

3 elements → 3! = 6 permutations
5 elements → 5! = 120 permutations
10 elements → 10! = 3,628,800 permutations

Example: The sequence [1, 2, 3] has these 6 permutations:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Sorting as Finding the Right Permutation

Among all n! permutations of a sequence, exactly one (for distinct elements) is the sorted permutation. Sorting is the process of finding and producing this specific permutation. For sequences with duplicate elements, there may be multiple permutations that satisfy the sorting constraint—more on this when we discuss stability.

The Sorting Problem as Permutation Selection:

Given n! possible arrangements, sorting algorithms must efficiently identify the one permutation where consecutive elements satisfy the ordering relation. A brute-force approach would be:

Generate all n! permutations
Check each one to see if it's sorted
Return the sorted one

This would be catastrophically slow—O(n! × n) time complexity. The genius of efficient sorting algorithms is that they find the correct permutation without explicitly enumerating all possibilities.

permutation_concept.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Illustrating sorting as permutation selection
from itertools import permutations
 
def find_sorted_permutation_brute_force(arr):
    """
    EXTREMELY INEFFICIENT - For illustration only.
    Demonstrates that sorting finds one permutation among n!
    """
    for perm in permutations(arr):
        # Check if this permutation is sorted
        is_sorted = all(perm[i] <= perm[i+1] for i in range(len(perm)-1))
        if is_sorted:
            return list(perm)
    return []  # Empty array is already sorted
 
# Example: [3, 1, 2] has 6 permutations
# Only [1, 2, 3] satisfies arr[i] <= arr[i+1] for all i
original = [3, 1, 2]
sorted_version = find_sorted_permutation_brute_force(original)
print(f"Original: {original}")
print(f"Sorted:   {sorted_version}")
 
# This approach is O(n! × n) - impractical for n > 10
# Real sorting algorithms are O(n log n) or better

The Formal Definition of Sorting

With total orderings and permutations understood, we can now state the formal definition of the sorting problem with mathematical precision.

Formal Definition: The Sorting Problem

Given:

A sequence A = [a₁, a₂, ..., aₙ] of n elements
A total ordering relation ≤ defined on the elements

Produce:

A sequence A' = [a'₁, a'₂, ..., a'ₙ] such that:
1. Permutation Property: A' is a permutation of A (same elements, possibly rearranged)
2. Ordering Property: For all i where 1 ≤ i < n: a'ᵢ ≤ a'ᵢ₊₁

The Two Correctness Criteria

A sorting algorithm is correct if and only if it satisfies BOTH properties: (1) the output contains exactly the same elements as the input, and (2) consecutive elements obey the ordering relation. Missing either property means the algorithm is broken.

Unpacking the Definition:

Property 1: Permutation (Conservation of Elements)

This says that sorting doesn't add, remove, or duplicate elements. Every element that goes in must come out exactly once. Mathematically:

The multiset of input elements equals the multiset of output elements
If input has three 5s, output must have exactly three 5s

Property 2: Ordering (Sorted Constraint)

This is the "sorted" part—each element is ≤ its successor. Notice:

We use ≤ not <, allowing equal consecutive elements
We only compare adjacent pairs (but transitivity implies the full ordering)
This defines non-decreasing order specifically

Valid Sorted Outputs

•[1, 2, 3] for input [3, 1, 2]
•[1, 1, 2, 3] for input [3, 1, 2, 1]
•[5] for input [5]
•[] for input []
•[3, 3, 3] for input [3, 3, 3]

Invalid Outputs (Why)

•[1, 2, 4] — changed element
•[1, 2] — missing element
•[1, 1, 2, 3] — wrong input specified
•[2, 1, 3] — not sorted
•[1, 3, 2] — not sorted

Mathematical Notation Deep Dive

For those who appreciate rigorous mathematical formalism, here's the sorting problem expressed in more precise notation. This level of formalism is what you'd encounter in academic algorithms textbooks and research papers.

Set-Theoretic Formulation:

Let:

A = (a₁, a₂, ..., aₙ) be an n-tuple (ordered sequence) of elements from a set S
(S, ≤) be a totally ordered set

Sorting produces a bijection (one-to-one mapping) π: {1, ..., n} → {1, ..., n} such that:

Permutation: The output is (a_{π(1)}, a_{π(2)}, ..., a_{π(n)})
Order Preservation: ∀i ∈ {1, ..., n-1}: a_{π(i)} ≤ a_{π(i+1)}

The bijection π describes which input position maps to which output position.

Why This Formalism Matters

This notation explicitly captures that sorting is a reordering (bijection on positions) that achieves ordered output. The permutation π is the "work" a sorting algorithm does—it computes which element goes where.

Alternative: Comparison Function Formulation

In practice, programming languages don't require a formal ≤ relation—they require a comparison function. This is a function cmp(a, b) that returns:

Negative value if a < b
Zero if a = b
Positive value if a > b

This comparison function must be:

Consistent with equality: cmp(a, a) = 0
Antisymmetric: sign(cmp(a, b)) = -sign(cmp(b, a))
Transitive: If cmp(a, b) < 0 and cmp(b, c) < 0, then cmp(a, c) < 0

Violating these properties leads to undefined behavior or incorrect sorting results.

comparison_function.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
from functools import cmp_to_key
 
def compare_integers(a: int, b: int) -> int:
    """
    A valid comparison function for integers.
    Returns: negative if a < b, zero if a == b, positive if a > b
    """
    return a - b
 
def compare_strings_by_length(s1: str, s2: str) -> int:
    """
    A valid comparison function: sorts strings by length.
    Shorter strings come first.
    """
    return len(s1) - len(s2)
 
def compare_people_by_age(person1: dict, person2: dict) -> int:
    """
    A valid comparison function for custom objects.
    Sorts people by age.
    """
    return person1['age'] - person2['age']
 
# Using comparison functions with Python's sort
numbers = [3, 1, 4, 1, 5, 9, 2, 6]
sorted_numbers = sorted(numbers, key=cmp_to_key(compare_integers))
print(f"Sorted numbers: {sorted_numbers}")
 
words = ["elephant", "cat", "dog", "butterfly", "ant"]
sorted_words = sorted(words, key=cmp_to_key(compare_strings_by_length))
print(f"Sorted by length: {sorted_words}")
 
people = [
    {'name': 'Alice', 'age': 30},
    {'name': 'Bob', 'age': 25},
    {'name': 'Charlie', 'age': 35}
]
sorted_people = sorted(people, key=cmp_to_key(compare_people_by_age))
print(f"Sorted by age: {[p['name'] for p in sorted_people]}")

Edge Cases in the Formal Definition

The formal definition handles edge cases that intuition might overlook. Understanding these cases is crucial for implementing robust sorting algorithms.

Case 1: Empty Sequence

Input: A = []

The permutation property is trivially satisfied (there's exactly one permutation of zero elements—the empty permutation). The ordering property is vacuously true (there are no pairs to compare). Therefore, [] is the correct sorted output.

Case 2: Single Element

Input: A = [x]

Again, both properties are trivially satisfied. [x] is already sorted. This is the simplest base case for recursive sorting algorithms.

Case 3: All Equal Elements

Input: A = [5, 5, 5, 5]

Any permutation satisfies the ordering property since 5 ≤ 5 is always true. All permutations are valid sorted outputs. In practice, most algorithms output the same sequence unchanged.

The Duplicate Element Challenge

When elements are duplicated, multiple permutations satisfy the sorting definition. For example, if input is [(Alice, 25), (Bob, 25)] sorted by age, both orderings are "correct." This is where stability becomes important—a topic we'll cover in detail later.

Case 4: Already Sorted Input

Input: A = [1, 2, 3, 4, 5]

The identity permutation (keeping everything in place) satisfies both properties. A good sorting algorithm should detect this and avoid unnecessary work. This is the "best case" for adaptive algorithms like Insertion Sort.

Case 5: Reverse Sorted Input

Input: A = [5, 4, 3, 2, 1]

Output must be [1, 2, 3, 4, 5]. Every element must move. This is often the "worst case" for certain algorithms.

Case 6: Floating-Point Considerations

Floating-point numbers introduce subtleties due to precision issues. The comparison function must handle:

Very small differences that might be numerical noise
Special values like NaN, Infinity, -Infinity
The fact that floating-point comparison is not always transitive due to rounding

Edge Case Summary
Edge Case	Input Example	Output	Algorithm Implication
Empty	[]	[]	Base case, return immediately
Single element	[x]	[x]	Base case, return immediately
All equal	[5, 5, 5]	[5, 5, 5]	Any permutation works
Already sorted	[1, 2, 3]	[1, 2, 3]	O(n) detection possible
Reverse sorted	[3, 2, 1]	[1, 2, 3]	Maximum work required
Two elements	[b, a]	[a, b]	Single comparison and potential swap

Verifying Sorting Correctness

The formal definition gives us a clear checklist for verifying whether an algorithm sorts correctly. We must verify both properties:

Verifying the Permutation Property:

We must confirm that output contains exactly the same elements as input. The most robust approach is to compare the multisets (also called bags) of input and output:

Count occurrences of each element in input
Count occurrences of each element in output
Verify the counts match for every element

Time complexity: O(n) with a hash map, O(n log n) with sorting

verify_sorting.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
from collections import Counter
from typing import List, TypeVar
 
T = TypeVar('T')
 
def verify_permutation_property(input_arr: List[T], output_arr: List[T]) -> bool:
    """
    Verify that output is a permutation of input.
    Uses Counter (multiset) comparison.
    """
    return Counter(input_arr) == Counter(output_arr)
 
def verify_ordering_property(arr: List, compare=lambda a, b: a <= b) -> bool:
    """
    Verify that array satisfies ordering property.
    Each element must be <= its successor according to compare function.
    """
    return all(compare(arr[i], arr[i+1]) for i in range(len(arr) - 1))
 
def verify_sorting_correctness(input_arr: List[T], output_arr: List[T],
                                compare=lambda a, b: a <= b) -> tuple[bool, str]:
    """
    Complete verification of sorting correctness.
    Returns (is_correct, message) tuple.
    """
    # Check permutation property
    if not verify_permutation_property(input_arr, output_arr):
        return False, "FAILED: Output is not a permutation of input"
    
    # Check ordering property
    if not verify_ordering_property(output_arr, compare):
        return False, "FAILED: Output is not properly ordered"
    
    return True, "PASSED: Sorting is correct"
 
# Test cases
test_cases = [
    ([3, 1, 4, 1, 5], [1, 1, 3, 4, 5]),  # Correct
    ([3, 1, 2], [1, 2, 4]),              # Wrong: changed element
    ([3, 1, 2], [2, 1, 3]),              # Wrong: not sorted
    ([], []),                             # Correct: empty
    ([42], [42]),                         # Correct: single element
]
 
for input_arr, output_arr in test_cases:
    is_correct, message = verify_sorting_correctness(input_arr, output_arr)
    print(f"Input: {input_arr} -> Output: {output_arr}")
    print(f"  {message}
")

Summary and Key Takeaways

We've established the formal mathematical foundation for understanding sorting. This precision isn't academic pedantry—it's the basis for:

Proving sorting algorithms correct
Understanding what makes one algorithm better than another
Handling edge cases properly
Building robust production software

Key Takeaways

•Sorting requires a total ordering — Elements must be pairwise comparable with a reflexive, antisymmetric, transitive, and total relation.
•Sorting produces a permutation — The output contains exactly the same elements as input, just rearranged.
•Two properties define correctness — Permutation property (same elements) + ordering property (consecutive elements obey ≤).
•Comparison functions implement orderings — They must satisfy consistency, antisymmetry, and transitivity.
•Edge cases are well-defined — Empty arrays, single elements, and all-equal elements have unambiguous correct outputs.
•Verification is computable — We can programmatically check both properties in O(n) time.

Foundation Established

You now have a rigorous understanding of what sorting means mathematically. This foundation prepares you for understanding why certain algorithms work, how to prove their correctness, and how to reason about their behavior. Next, we'll explore the difference between ascending and descending order, and how the formal definition adapts to each.

Looking Ahead:

With the formal definition established, the next page examines ascending versus descending order—how we flip the ordering relation and what implications this has for algorithm implementation and API design.