String Comparison, Ordering & Equality

Consider sorting these German words: ["Öl", "Apfel", "Öffnung", "Zebra"]

In German locale: ["Apfel", "Öffnung", "Öl", "Zebra"]

• Ö is treated like O, sorting after A but before Z

In Swedish locale: ["Apfel", "Zebra", "Öffnung", "Öl"]

• Ö is a distinct letter that comes after Z!

Using pure ASCII/binary comparison: ["Apfel", "Zebra", "Öffnung", "Öl"]

• Ö (code 214) comes after Z (code 90) because 214 > 90

Three different sorting approaches produce two different results. Which is correct?

The answer is: it depends on context. This is the domain of locale-aware versus binary comparison—a distinction that determines whether your software feels native to users across cultures or produces results that seem arbitrarily wrong.

Definition:

Binary comparison (also called ordinal comparison or code point comparison) compares strings by their raw numeric values—the Unicode code points (or bytes in ASCII) that represent each character.

How it works:

1. Compare strings character by character from left to right
2. At each position, compare the numeric code point of each character
3. The first differing code point determines the result
4. If one string is a prefix of the other, the shorter string is 'less than'

This is pure lexicographical comparison on numeric values:

"Apfel" vs "Öl"

Position 0: 'A' (65) vs 'Ö' (214)
65 < 214, so "Apfel" < "Öl"

Binary sorted: ["Apfel", "Zebra", "Öffnung", "Öl"]
// Z (90) < Ö (214), so Z comes first

Characteristics of Binary Comparison:

Advantages:

• Deterministic: Same input always produces same output, regardless of system settings
• Fast: Direct numeric comparison, no table lookups required
• Simple: Easy to understand, implement, and verify
• Consistent across systems: No dependence on installed locales or libraries
• Stable for identifiers: Perfect for comparing code, keys, and technical strings

Disadvantages:

• Culturally incorrect: Produces ordering that violates human expectations in many languages
• Case quirks: All uppercase letters sort before all lowercase ('Z' < 'a')
• Accent placement: Characters like 'é', 'ñ', 'ü' sort after 'z', not with their base letters
• Inappropriate for user-facing sorting: Users expect culturally appropriate order

Definition:

Locale-aware comparison (also called collation or cultural comparison) sorts strings according to the conventions of a specific language and culture. It treats strings as text meant for human consumption, not as sequences of bytes.

How it works (conceptually):

1. Transform each character to a collation key based on the locale
2. Collation keys encode sorting weight at multiple levels:
   • Primary: Base letter (a, b, c...)
   • Secondary: Accents and diacritics (a vs á vs ä)
   • Tertiary: Case (a vs A)
   • Quaternary: Punctuation and special characters
3. Compare collation keys to determine order

The result matches human expectations for that culture:

German locale sorting:
"Öl" is treated like "Ol" at primary level
→ Sorts after "O" words, before "P" words
→ ["Apfel", "Öffnung", "Öl", "Zebra"]

Locale Variations in Action:

German (de_DE):

• Treats ä, ö, ü as variants of a, o, u
• ß is equivalent to 'ss' for sorting
• "Männer" sorts near "Manner", not after 'z'

Swedish (sv_SE):

• Treats ä, ö as separate letters that come after z
• Alphabet ends: ...x, y, z, å, ä, ö
• "Öl" sorts after "Zebra"

Spanish (es_ES):

• Historically treated "ch" as a single letter after "c"
• "ñ" is a separate letter after "n"
• Modern Spanish often uses standard Latin ordering

Estonian (et_EE):

• "z" comes in the middle of the alphabet, not at the end!
• Alphabet: ...s, z, t, u...x, y

Japanese:

• Multiple sort orders exist (hiragana, katakana, kanji readings)
• Collation is vastly more complex than Latin alphabets

The Unicode Collation Algorithm (UCA) is the standard specification for sorting strings in a linguistically and culturally correct manner. It's the foundation of locale-aware sorting in most modern systems.

Core Concepts:

1. Collation Elements:

Each character (or sequence of characters) maps to a collation element—a tuple of numeric weights at different levels.

Example collation elements (simplified):
'a' → [0A0A, 0020, 0002]  // Primary, Secondary, Tertiary
'A' → [0A0A, 0020, 0008]  // Same primary/secondary, different tertiary
'á' → [0A0A, 0024, 0002]  // Same primary, different secondary (accent)
'ä' → [0A0A, 0028, 0002]  // Same primary, different secondary (diaeresis)

2. Multi-Level Comparison:

Strings are compared level by level:

• First, compare all primary weights
• If equal at primary level, compare secondary weights
• If still equal, compare tertiary weights
• And so on for additional levels

This allows 'a' and 'A' and 'á' to be near each other (same primary) while still having a defined order.

3. Collation Tailoring:

The UCA defines a Default Unicode Collation Element Table (DUCET)—a default sorting order for all Unicode characters. Specific locales then tailor this default:

DUCET default: ä sorts after z (by code point convention)

German tailoring: ä sorts as if it were 'ae' or just after 'a'
Swedish tailoring: ä sorts after z (happens to match DUCET here)

4. Normalization:

Collation typically normalizes strings first. Characters like 'é' can be represented as:

• Precomposed: single code point U+00E9
• Decomposed: 'e' (U+0065) + combining acute (U+0301)

Both representations should collate identically, so normalization is essential.

5. Variable Weighting:

Punctuation and spaces can be handled differently:

• Non-ignorable: Spaces and punctuation affect sort order
• Blanked/Shifted: Spaces and punctuation are ignored at primary level

This determines whether "can't" sorts near "cant" or is separated by the apostrophe.

The choice between binary and locale-aware comparison depends on what the strings represent and who will see the results:

Use Binary Comparison When:

1. Comparing technical identifiers: Variable names, constants, API keys, UUIDs
2. Hash table keys and lookups: Need exact matching
3. Sorting for machine consumption: Indexing, deduplication, technical ordering
4. Reproducibility is required: Tests, deterministic algorithms
5. Performance is critical: Binary comparison is faster
6. Cross-system consistency: No dependency on locale installation

Use Locale-Aware Comparison When:

1. Displaying sorted data to users: Name lists, product catalogs, search results
2. User input comparison: Usernames, search queries
3. Natural language text: Documents, content, titles
4. Internationalized applications: Serving users in multiple locales
5. Matching cultural expectations: Phone books, dictionaries

Here's how to implement each comparison approach in common programming environments:

Binary Comparison:

// JavaScript - binary comparison
"apple".localeCompare("Banana", undefined, { sensitivity: 'variant', usage: 'sort' })
// Or simply use < and > operators for binary comparison
"apple" < "Banana"  // true: 'a' (97) > 'B' (66), so false wait...
// Actually: 'a' (97) > 'B' (66) is true, so "apple" > "Banana"

// Python - binary comparison is default
sorted(["apple", "Banana"])  // ['Banana', 'apple']

// Java - binary comparison
String.compareTo()  // Uses code point values

Locale-Aware Comparison:

// JavaScript - locale-aware
["apple", "Banana"].sort((a, b) => a.localeCompare(b))
// Result: ['apple', 'Banana'] - case-insensitive by default

// With specific locale
["Öl", "Ol"].sort((a, b) => a.localeCompare(b, 'de'))
// German locale: Ö sorts with O

Python with Locale:

import locale

# Set locale
locale.setlocale(locale.LC_ALL, 'de_DE.UTF-8')

# Sort with locale awareness
sorted(["Öl", "Apfel", "Zebra"], key=locale.strxfrm)
# Result depends on German collation rules

# Or use ICU directly
import icu  # PyICU library
collator = icu.Collator.createInstance(icu.Locale('de_DE'))
sorted(words, key=collator.getSortKey)

Database Queries:

-- PostgreSQL with specific collation
SELECT * FROM products ORDER BY name COLLATE "de_DE";

-- MySQL
SELECT * FROM products ORDER BY name COLLATE utf8mb4_german2_ci;

-- SQLite (limited collation support)
SELECT * FROM products ORDER BY name COLLATE NOCASE;  -- Case-insensitive only

Key Insight: Most standard library sort functions use binary comparison by default. Locale-aware sorting typically requires explicit configuration.

Binary and locale comparison have significantly different performance characteristics:

Binary Comparison Performance:

• Time complexity: O(min(n, m)) where n and m are string lengths
• Work per character: ~1 operation (direct numeric comparison)
• Memory: O(1) — no additional memory needed
• Caching: Compiler can optimize heavily

Locale-Aware Comparison Performance:

• Time complexity: O(n × k) where k is the complexity factor from collation
• Work per character: Multiple operations (table lookup, weight extraction, multi-level comparison)
• Memory: May allocate collation keys (O(n) per string)
• Caching: Limited optimization possible due to complexity

Typical Performance Difference:

Locale comparison is often 3-10x slower than binary comparison, depending on:

• Locale complexity
• String length
• Implementation quality

Optimization Strategies:

1. Precompute Sort Keys:

For repeated sorting, compute collation keys once and sort by keys:

# Instead of sorting with locale comparison each time
sorted(words, key=locale.strxfrm)

# Precompute keys for multiple sorts
keys = {word: locale.strxfrm(word) for word in words}
sorted(words, key=lambda w: keys[w])  # Use precomputed keys

2. Two-Phase Sorting:

For large datasets where most items have clear order:

• First pass: binary sort (fast)
• Second pass: locale sort only within ambiguous groups

3. Lazy Evaluation:

For user interfaces showing sorted lists:

• Sort only visible items initially
• Sort remaining items on scroll/request

4. Hybrid Approaches:

Store both raw strings and collation keys:

• Use collation keys for sorting and range queries
• Use raw strings for display and exact matching

Both comparison approaches have traps for the unwary:

Pitfall 1: Mixing Comparison Types

Using binary comparison for one operation and locale comparison for another on the same data:

Data stored sorted with binary comparison
→ Binary search works

User interface sorts with locale comparison  
→ Display order differs from storage order
→ Pagination and scrolling break!

Solution: Always use consistent comparison within a data pipeline.

Pitfall 2: Locale Environment Variability

Development machine: Locale data for all languages installed
Production server: Minimal Docker image, no locale data

Result: Code works locally, breaks in production

Solution: Explicitly install locale data in deployment or use locale-independent ICU libraries.

Pitfall 3: Default Locale Surprises

System default locale varies between machines:

Developer in US: en_US sort order
Server in Germany: de_DE sort order
Test server in Japan: ja_JP sort order

All produce different results for the same data!

Solution: Always specify locale explicitly; never rely on system default.

Pitfall 4: Binary Search on Locale-Sorted Data

Data sorted with locale comparison
Binary search using binary comparison

Binary search assumes: if A < B and B < C, then A < C
But locale vs binary comparison may disagree on these relationships!

Result: Binary search fails or misses elements

Solution: Sort and search must use the same comparison.

Pitfall 5: Hash Tables with Locale Keys

// Stored with one normalization
map["café"] = value

// Looked up with different normalization
map["café"]  // Different underlying bytes!

Result: Key not found

Solution: Use Unicode normalization before hashing. Use exact binary comparison for hash keys.

Pitfall 6: Ignoring Locale in User-Facing Data

App displays: ["Zoo", "apple", "Öl"]
User expects: ["apple", "Öl", "Zoo"] (German user)

Result: App feels 'broken' or 'foreign'

Solution: Detect or allow user to select locale for display sorting.

We've explored the fundamental distinction between binary and locale-aware string comparison—two approaches that can produce very different results from the same input. Let's consolidate the essential knowledge:

What's next:

Comparing strings for ordering is one challenge. Comparing strings for equality is another—with its own subtleties. The next page explores equality vs identity—when two strings are 'equal' versus 'identical', how different programming languages handle this distinction, and why it matters for correctness and performance.