Introduction to Sorting

Sorting rearranges records according to an ordering, often enabling faster searches, grouping and greedy choices. Ascending order puts smaller keys first; descending order reverses that relation. Sorting values is simple, but sorting records raises additional questions: what happens to equal keys, what must remain associated, and how much extra memory is needed? We demonstrate stable sorting of score-and-name records.

Prerequisites: Structs; STL Essentials; complexity.

Build the idea

1. 1. Specify the sort key

   Each record contains a score and a name. We sort by score only, so equal-score names are equivalent for this ordering. The comparator returns a.score<b.score. It must be strict: comparing an item with itself must be false. Using <= violates the ordering contract and can make library sorting behavior invalid.

2. 2. Define stability

   A stable sort preserves the original relative order of equal keys. For input (2,A),(1,B),(2,C), stable ascending output is (1,B),(2,A),(2,C). An unstable sort may exchange A and C while still correctly sorting scores. std::sort does not promise stability; std::stable_sort does. If tie order must follow a different rule, explicitly include that secondary key rather than relying on stability alone.

3. 3. Separate stability from storage

   In-place usually means O(1) extra array storage, sometimes discussing recursion stack separately; state the convention. A stable algorithm need not be in-place, and an in-place algorithm need not be stable. Selection sort swaps distant elements and is usually unstable; insertion sort with strict shifts can be stable. Merge sort’s usual array implementation uses an extra buffer.

4. 4. Compare algorithm families

   General comparison sorting requires Ω(n log n) comparisons in the worst case for arbitrary distinct keys. std::sort guarantees O(n log n) comparisons in C++17. Simple bubble, selection and insertion methods have quadratic worst cases; merge sort guarantees n log n; quicksort has expected/average n log n under suitable pivot assumptions but quadratic worst cases. Counting/radix exploit key representation and do not contradict comparison lower bounds.

5. 5. Trace the output

   Read scores 2,1,2 associated with A,B,C. The stable comparator moves B ahead, then keeps A before C. Sorting the scores independently from names would lose associations; store each record together. A later need for original order can be handled by retaining an original index. The example also handles zero records without dereferencing an element.

This is a complete program. Compile with C++17 and enter the input described below.

// Key idea: 5. Trace the output Read scores 2,1,2 associated with A,B,C.
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
struct Record{
    int score;
    std::string name;
};
bool byScore(const Record&a,const Record&b){
    return a.score<b.score;
}
int main(){
    int n;
    std::cin>>n;
    std::vector<Record>records(n);
    for(auto&item:records){
        std::cin>>item.score>>item.name;
    }
    std::stable_sort(records.begin(),records.end(),byScore);
    for(const auto&item:records){
        std::cout<<item.score<<' '<<item.name<<'\n';
    }
}

Complexity analysis

std::stable_sort uses O(n log n) comparisons when sufficient extra memory is available, and up to O(n log²n) comparisons otherwise in C++17. Typical buffered implementations use O(n) extra element storage; do not claim a universal constant-space guarantee. Input records occupy O(n) objects plus name characters; comparison here checks integer scores only.

Example input and output

Read n (0..10000), then n lines score name with a one-token name. Output records by ascending score, preserving input order for equal scores.

Input

3
2 A
1 B
2 C

Output

1 B
2 A
2 C

B has the smallest score; A and C both score 2 and keep their input order.

Practical applications

Use sorting to bring equal keys together, enable binary search, compare multisets or prepare two-pointer/greedy scans. Prefer standard library sorting in ordinary contest solutions; learn manual algorithms to understand guarantees and special constraints. Choose stable sorting when original tie order is part of the output contract.

Check your understanding

What does sorting stability preserve?

Put it into practice

Create a stable descending comparator and test equal scores.