# arthkamboj/parallel-mergesort architecture

> Architecture diagram of the GitHub repository arthkamboj/parallel-mergesort, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-06-15). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/arthkamboj/parallel-mergesort
- Repository: https://github.com/arthkamboj/parallel-mergesort

## Overview

1. **Repository shape**
   - This is a small, header-only C++ sorting library centered on `src/fast_sort.h`.
   - `src/main.cpp` is a usage/demo entry point, and `src/main.exe` is a generated binary artifact, not a source subsystem.

2. **Primary architectural boundary**
   - The library exposes a template sorter API to application code, likely as `ParallelSorter<T>`.
   - The consuming program provides a container of elements; the sorter owns the orchestration of parallelism, temporary memory, and algorithm selection.

3. **Top-level sort pipeline**
   - The core algorithm is a merge-sort-based pipeline with recursive subdivision, local sorting of small ranges, and merge phases to combine results.
   - The sort entry point allocates or initializes shared state once, then drives the recursion tree through parallel or sequential branches depending on size and depth.

4. **Parallel execution model**
   - The parallel subsystem uses a decentralized work-stealing design rather than a single global queue.
   - Each worker thread maintains its own deque protected by a `CRITICAL_SECTION`; workers prefer local work and only steal when idle, which reduces contention on shared synchronization primitives.

5. **Task scheduling and load balancing**
   - Recursive sort work is turned into tasks that can be pushed onto worker-local queues.
   - The scheduler limits over-parallelization with two gates: a minimum problem size threshold and a maximum recursion depth based on core count, so the system does not keep spawning tasks after available CPU parallelism is saturated.

6. **Worker thread lifecycle**
   - Idle workers do not block immediately; they first spin using `_mm_pause()` and then yield with `SwitchToThread()` if no work appears.
   - This design targets low-latency task pickup for short-lived merge/sort jobs while still avoiding a pure busy-wait when the machine is saturated.

7. **SIMD acceleration path**
   - Integer-heavy merge/copy operations use AVX2 intrinsics through `__m256i`, moving 256 bits at a time.
   - The implementation is template-specialized so that arithmetic types like `int` can take the SIMD fast path, while non-vector-friendly types fall back to the generic implementation.

8. **Sequential fallback path**
   - Small subarrays bypass the parallel scheduler and use an optimized sequential sort.
   - This boundary is important to the architecture: the library intentionally trades parallelism for lower overhead below the configured threshold.

9. **Memory management model**
   - The algorithm uses a single auxiliary scratchpad buffer allocated once per top-level sort.
   - That buffer is threaded through recursive calls, avoiding repeated heap allocations and reducing cross-thread allocator contention during merge phases.

10. **Platform and runtime dependencies**
   - The implementation is Windows-specific in practice because it relies on Windows threading primitives and scheduling calls.
   - AVX2 support is required for the optimized integer path, and the build flags in the README reflect that the architecture depends on compiler support for both optimization and x86 SIMD extensions.

11. **How data flows through the system**
   - Application code calls the sorter with a collection.
   - The sorter partitions the input recursively, schedules work onto worker-local queues, performs local sorts or merges, uses the shared scratch buffer for merging, and finally writes the sorted result back to the caller’s container.

12. **What is not present**
   - There is no visible multi-module service boundary, no networking, no persistence layer, and no external runtime dependency beyond the OS and CPU features.
   - Architecturally, this is a single-library computational engine with a thin demo application around it.

Main entry points: [`src/fast_sort.h`](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h) (Partitioning), [`src/main.cpp`](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/main.cpp) (Demo main)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_grp_app["Demo app"]
  node_n_main["Demo main<br/>app entry<br/>[main.cpp]"]
end

subgraph group_grp_lib["Sort library"]
  node_n_api["Sorter API<br/>template facade<br/>[fast_sort.h]"]
  node_n_orchestrator["Sort orchestrator<br/>control core<br/>[fast_sort.h]"]
  node_n_partition{{"Partitioning<br/>recursion<br/>[fast_sort.h]"}}
  node_n_threshold(("Size gate<br/>policy<br/>[fast_sort.h]"))
  node_n_depth(("Depth gate<br/>policy<br/>[fast_sort.h]"))
  node_n_seqsort["Seq sort<br/>sequential fallback<br/>[fast_sort.h]"]
  node_n_merge["Merge phase<br/>merge core<br/>[fast_sort.h]"]
  node_n_scratch[("Scratch buffer<br/>aux memory<br/>[fast_sort.h]")]
  node_n_tasks{{"Task builder<br/>work items<br/>[fast_sort.h]"}}
  node_n_sched["Work stealing<br/>scheduler<br/>[fast_sort.h]"]
  node_n_deque["Local deque<br/>worker queue<br/>[fast_sort.h]"]
  node_n_worker["Worker loop<br/>thread runtime<br/>[fast_sort.h]"]
  node_n_spin(("Spin wait<br/>idle policy<br/>[fast_sort.h]"))
  node_n_yield(("Thread yield<br/>idle policy<br/>[fast_sort.h]"))
  node_n_simd["AVX2 path<br/>simd accel<br/>[fast_sort.h]"]
  node_n_fallback["Generic path<br/>template fallback<br/>[fast_sort.h]"]
  node_n_platform(("Windows runtime<br/>os dependency<br/>[fast_sort.h]"))
end

node_n_main -->|"calls"| node_n_api
node_n_api -->|"enters"| node_n_orchestrator
node_n_orchestrator -->|"subdivides"| node_n_partition
node_n_partition -->|"checks"| node_n_threshold
node_n_partition -->|"checks"| node_n_depth
node_n_partition -->|"fallback"| node_n_seqsort
node_n_partition -->|"spawns"| node_n_tasks
node_n_tasks -->|"enqueued by"| node_n_sched
node_n_sched -->|"uses"| node_n_deque
node_n_sched -->|"runs on"| node_n_worker
node_n_worker -->|"idles with"| node_n_spin
node_n_spin -->|"then"| node_n_yield
node_n_sched -->|"depends on"| node_n_platform
node_n_orchestrator -->|"allocates"| node_n_scratch
node_n_partition -->|"merges with"| node_n_merge
node_n_merge -->|"reuses"| node_n_scratch
node_n_merge -->|"specializes to"| node_n_simd
node_n_merge -->|"falls back to"| node_n_fallback

click node_n_main "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/main.cpp"
click node_n_api "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_orchestrator "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_partition "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_threshold "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_depth "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_seqsort "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_merge "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_scratch "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_tasks "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_sched "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_deque "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_worker "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_spin "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_yield "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_simd "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_fallback "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"
click node_n_platform "https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_n_main toneBlue
class node_n_api,node_n_orchestrator,node_n_partition,node_n_threshold,node_n_depth,node_n_seqsort,node_n_merge,node_n_scratch,node_n_tasks,node_n_sched,node_n_deque,node_n_worker,node_n_spin,node_n_yield,node_n_simd,node_n_fallback,node_n_platform toneAmber
```

## Components

### Demo app

Usage entry point and example consumer

- [Demo main](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/main.cpp): app entry · Usage and demonstration entry point · `src/main.cpp`

### Sort library

Header-only parallel merge-sort engine

- [Sorter API](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): template facade · Public sorter interface used by application code · `src/fast_sort.h`
- [Sort orchestrator](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): control core · Top-level sort driver that sets up shared state and launches work · `src/fast_sort.h`
- [Partitioning](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): recursion · Splits the input into smaller ranges for recursive processing · `src/fast_sort.h`
- [Size gate](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): policy · Limits parallelization for small subarrays · `src/fast_sort.h`
- [Depth gate](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): policy · Caps recursion depth based on available parallelism · `src/fast_sort.h`
- [Seq sort](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): sequential fallback · Optimized local sort for small ranges · `src/fast_sort.h`
- [Merge phase](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): merge core · Combines sorted subranges during the merge-sort pipeline · `src/fast_sort.h`
- [Scratch buffer](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): aux memory · Single shared temporary buffer reused across recursive calls · `src/fast_sort.h`
- [Task builder](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): work items · Turns recursive sort work into schedulable tasks · `src/fast_sort.h`
- [Work stealing](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): scheduler · Decentralized scheduler that prefers local work and steals when idle · `src/fast_sort.h`
- [Local deque](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): worker queue · Per-worker task deque protected by a critical section · `src/fast_sort.h`
- [Worker loop](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): thread runtime · Worker lifecycle with spin, pause, and yield behavior · `src/fast_sort.h`
- [Spin wait](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): idle policy · Short idle phase using processor pause instructions · `src/fast_sort.h`
- [Thread yield](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): idle policy · Falls back to OS thread yielding when no work is available · `src/fast_sort.h`
- [AVX2 path](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): simd accel · Vectorized merge and copy operations for arithmetic types · `src/fast_sort.h`
- [Generic path](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): template fallback · Non-vectorized implementation for other element types · `src/fast_sort.h`
- [Windows runtime](https://github.com/arthkamboj/parallel-mergesort/blob/main/src/fast_sort.h): os dependency · Uses Windows threading and scheduling primitives · `src/fast_sort.h`

## Connections

- Demo main → Sorter API: calls · Demo program invokes the sorter
- Sorter API → Sort orchestrator: enters · Public API forwards to the top-level sort driver
- Sort orchestrator → Partitioning: subdivides · Driver recursively partitions the input range
- Partitioning → Size gate: checks · Uses problem-size threshold before spawning work
- Partitioning → Depth gate: checks · Uses depth cap to avoid over-parallelization
- Partitioning → Seq sort: fallback · Small ranges are sorted locally
- Partitioning → Task builder: spawns · Parallel branches become schedulable tasks
- Task builder → Work stealing: enqueued by · Tasks are submitted to the work-stealing scheduler
- Work stealing → Local deque: uses · Each worker maintains a local deque
- Work stealing → Worker loop: runs on · Scheduler is executed by worker threads
- Worker loop → Spin wait: idles with · Workers first spin briefly when idle
- Spin wait → Thread yield: then · Idle workers yield if no work appears
- Work stealing → Windows runtime: depends on · Relies on Windows synchronization and scheduling calls
- Sort orchestrator → Scratch buffer: allocates · Top-level sort creates one shared scratch buffer
- Partitioning → Merge phase: merges with · Recursive results flow into merge phases
- Merge phase → Scratch buffer: reuses · Merges read and write through the shared auxiliary buffer
- Merge phase → AVX2 path: specializes to · Arithmetic types use the AVX2 fast path
- Merge phase → Generic path: falls back to · Other types use the generic implementation