Sorting Algorithms

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Merge two sorted ranges [l, m) and [m, r) into tmp, then copy back to a
5
static void merge_ranges(vector<int>& a, vector<int>& tmp, int l, int m, int r) {
6
    int i = l, j = m, k = l;
7
    while (i < m && j < r) {
8
        // Stable: when a[i] == a[j], take from left first
9
        if (a[i] <= a[j]) tmp[k++] = a[i++];
10
        else tmp[k++] = a[j++];
11
    }
12
    while (i < m) tmp[k++] = a[i++];
13
    while (j < r) tmp[k++] = a[j++];
14
    // Copy merged result back to a
15
    for (int t = l; t < r; ++t) a[t] = tmp[t];
16
}
17
18
static void merge_sort_rec(vector<int>& a, vector<int>& tmp, int l, int r) {
19
    if (r - l <= 1) return; // 0 or 1 element is already sorted
20
    int m = l + (r - l) / 2;
21
    merge_sort_rec(a, tmp, l, m);
22
    merge_sort_rec(a, tmp, m, r);
23
    // Optimization: if already ordered, skip merge
24
    if (a[m - 1] <= a[m]) return;
25
    merge_ranges(a, tmp, l, m, r);
26
}
27
28
void merge_sort(vector<int>& a) {
29
    vector<int> tmp(a.size()); // O(n) auxiliary buffer reused across merges
30
    merge_sort_rec(a, tmp, 0, (int)a.size());
31
}
32
33
int main() {
34
    ios::sync_with_stdio(false);
35
    cin.tie(nullptr);
36
37
    vector<int> a = {5, 1, 4, 2, 8, 5, 3, 5};
38
    merge_sort(a);
39
    for (int x : a) cout << x << ' ';
40
    cout << "\n";
41
    return 0;
42
}
43

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
static std::mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
5
6
// Partition a[l..r] into < pivot, == pivot, > pivot. Returns pair {lt_end, gt_begin}.
7
static pair<int,int> partition3(vector<int>& a, int l, int r, int pivot) {
8
    int i = l, lt = l, gt = r;
9
    while (i <= gt) {
10
        if (a[i] < pivot) swap(a[i++], a[lt++]);
11
        else if (a[i] > pivot) swap(a[i], a[gt--]);
12
        else i++;
13
    }
14
    return {lt, gt + 1}; // [l, lt) < pivot, [lt, gt+1) == pivot, [gt+1, r+1) > pivot
15
}
16
17
void quicksort(vector<int>& a, int l, int r) {
18
    while (l < r) {
19
        // Switch to insertion sort for tiny segments to improve constants
20
        if (r - l + 1 <= 16) {
21
            for (int i = l + 1; i <= r; ++i) {
22
                int x = a[i], j = i - 1;
23
                while (j >= l && a[j] > x) { a[j + 1] = a[j]; --j; }
24
                a[j + 1] = x;
25
            }
26
            return;
27
        }
28
        uniform_int_distribution<int> dist(l, r);
29
        int pivot = a[dist(rng)];
30
        auto [lt, gt] = partition3(a, l, r, pivot);
31
        // Recurse on smaller side to bound recursion depth, loop on larger side
32
        if (lt - l < r - gt + 1) {
33
            if (l < lt - 1) quicksort(a, l, lt - 1);
34
            l = gt; // tail-recurse on the larger part via loop
35
        } else {
36
            if (gt < r) quicksort(a, gt, r);
37
            r = lt - 1; // continue on the other side
38
        }
39
    }
40
}
41
42
int main() {
43
    ios::sync_with_stdio(false);
44
    cin.tie(nullptr);
45
46
    vector<int> a = {9, 3, 5, 3, 3, 8, 2, 7, 6, 3, 1, 0, 3};
47
    quicksort(a, 0, (int)a.size() - 1);
48
    for (int x : a) cout << x << ' ';
49
    cout << '\n';
50
    return 0;
51
}
52

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
void counting_sort(vector<int>& a) {
5
    if (a.empty()) return;
6
    int mn = *min_element(a.begin(), a.end());
7
    int mx = *max_element(a.begin(), a.end());
8
    long long K = 1LL * mx - mn + 1; // key range size
9
    if (K > 2e7) {
10
        // Guard: range too large for counting sort memory in typical settings
11
        throw runtime_error("Range too large for counting sort");
12
    }
13
    vector<int> cnt((size_t)K, 0);
14
    for (int x : a) cnt[x - mn]++;
15
    // Prefix sums to get positions (stable placement)
16
    for (size_t i = 1; i < cnt.size(); ++i) cnt[i] += cnt[i - 1];
17
    vector<int> out(a.size());
18
    // Traverse from right to left for stability
19
    for (int i = (int)a.size() - 1; i >= 0; --i) {
20
        int key = a[i] - mn;
21
        out[--cnt[key]] = a[i];
22
    }
23
    a.swap(out);
24
}
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    vector<int> a = {5, -2, 7, 5, 0, -2, 3, 5};
31
    try {
32
        counting_sort(a);
33
        for (int x : a) cout << x << ' ';
34
        cout << '\n';
35
    } catch (const exception& e) {
36
        cerr << "Error: " << e.what() << '\n';
37
    }
38
    return 0;
39
}
40

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Item {
5
    int key;    // primary key to sort by
6
    int id;     // original position (to observe stability)
7
};
8
9
int main() {
10
    ios::sync_with_stdio(false);
11
    cin.tie(nullptr);
12
13
    vector<Item> v = {{5,0},{3,1},{5,2},{2,3},{5,4},{3,5}};
14
15
    auto cmp_key = [](const Item& a, const Item& b){ return a.key < b.key; };
16
17
    // Copy for two different sorts
18
    auto a = v, b = v;
19
20
    // std::sort is a fast hybrid (introsort) but not stable
21
    sort(a.begin(), a.end(), cmp_key);
22
23
    // std::stable_sort preserves the relative order of equal keys
24
    stable_sort(b.begin(), b.end(), cmp_key);
25
26
    cout << "std::sort order (key,id):\n";
27
    for (auto &x : a) cout << '(' << x.key << ',' << x.id << ") ";
28
    cout << "\n\nstd::stable_sort order (key,id):\n";
29
    for (auto &x : b) cout << '(' << x.key << ',' << x.id << ") ";
30
    cout << '\n';
31
    return 0;
32
}
33