A C++ benchmark that compares sequential, process-based, and thread-based partitioned sorting with a single-process QuickSort baseline.
這個專案比較資料切割、合併與平行化策略對排序效能的影響，包含單一 Bubble Sort、分段循序排序、多程序共享記憶體、多執行緒，以及 QuickSort 基準。它不只展示 API 使用，也保留了 N、K 與執行時間之間的實驗分析。
| Method | Strategy | Parallel mechanism |
|---|---|---|
| 1 | Bubble Sort over the complete input | None |
| 2 | Split into K segments, sort sequentially, merge hierarchically | None |
| 3 | Sort and merge segments in child processes | fork, waitpid, System V shared memory |
| 4 | Sort and merge segments with worker threads | std::thread, shared address space |
| 5 | In-place QuickSort baseline | None |
Method 3 is available on Linux. On other platforms the program reports that the process-based implementation requires Linux/WSL. The remaining methods are portable C++17.
Input integers
-> K balanced segments
-> per-segment Bubble Sort
-> pairwise parallel/sequential merge rounds
-> sorted output + elapsed time
The process implementation places the source and temporary merge buffers in System V shared memory so forked workers can operate on common data. The thread implementation uses the same segment and merge structure within one address space, avoiding explicit inter-process data transfer.
Requirements:
- CMake 3.20 or later
- A C++17 compiler
- Python 3 for the test runner
cmake -S . -B build
cmake --build build --config ReleaseThe program asks for:
- Input path without the
.txtextension. - Number of partitions K.
- Method number from 1 to 5.
Example on Bash:
printf "examples/input_small\n4\n4\n" | ./build/parallel-sortExample on PowerShell:
"examples/input_small`n4`n4" | .\build\Release\parallel-sort.exeThe result is written next to the input file as input_small_output4.txt and contains the sorted values, measured CPU time, and output timestamp.
ctest --test-dir build --output-on-failure -C ReleaseThe automated test runner executes methods 1, 2, 4, and 5 on every platform; it additionally verifies the fork/shared-memory method on Linux. Each output file is parsed to confirm complete sorted order and required timing metadata.
The original experiment compared up to one million integers and multiple K values. The most important conclusion was that algorithmic complexity dominated the parallelization gains: the single-process QuickSort baseline remained dramatically faster than partitioned Bubble Sort, even when the latter used processes or threads.
See benchmark summary for the preserved measurements and interpretation. These are historical measurements from the coursework environment, not claims about current hardware.
.
├── src/parallel_sort.cpp
├── tests/verify_sorting.py
├── examples/input_small.txt
├── docs/benchmark-summary.md
├── .github/workflows/build.yml
├── CMakeLists.txt
└── README.md
This is a portfolio edition of an individual university Operating Systems project. Large generated inputs and dozens of repeated output files are excluded; the repository contains a compact fixture and a test runner that regenerates evidence as needed.
The original mixed source encoding was normalized to UTF-8, personal grading metadata was removed, and non-standard <bits/stdc++.h> usage was replaced with explicit standard headers for portability.
- Bubble Sort is intentionally retained because the experiment studies partitioning and parallel execution overhead, not because it is recommended for production sorting.
- Method 3 depends on Linux process and System V IPC facilities.
- The original timing format measures wall-clock elapsed milliseconds despite the historical output label
CPU Time. - Fresh cross-platform build results will be confirmed by CI after publication.
No open-source license has been selected yet. A license will be added only after the publication and ownership review is complete.