Artificial Sort: An In-Situ Divide-and-Conquer Sorting Algorithm with O(1) Auxiliary Heap Memory via Half-Pass Traversal and Dynamic In-Stream Buffering

Textbook formulations of standard merge sort require O(N) auxiliary heap memory, creating severe Out-Of-Memory (OOM) vulnerabilities in resource-constrained embedded systems and IoT sensor nodes. Conversely, established O(1)-auxiliary-space in-place merge algorithms (e.g., Kronrod, Huang-Langston, SymMerge, GrailSort) rely on complex block-tagging, internal unique-key extraction, and multi-pass block reversal routines requiring 300 to 1,500 lines of arcane code. This paper presents Artificial Sort, a novel in-situ divide-and-conquer sorting algorithm that achieves strict O(1) auxiliary heap memory (0 dynamic heap bytes) within approximately 35 lines of idiomatic C. By restricting the primary merge loop strictly to the first half (l ≤ mid, formalized herein as the Half-Pass Principle), the algorithm utilizes the right partition as a virtual dual-stream buffer: Stream A for displaced left elements and Stream B for untouched original right elements. We present rigorous induction proofs for the monotonicity of the displaced virtual buffer (Invariant 1) and terminal left-partition optimality (Invariant 2). We mathematically prove a strict O(log N) logarithmic upper bound on recursion stack depth, confirmed empirically with a maximum of only 26 stack frames for N = 50,000 elements (< 1 KB stack footprint). Multi-tier stress testing across six independent tiers confirms that Artificial Sort maintains O(N) best-case, O(N log N) average-case, and bounded O(N^2) worst-case execution with an unusually low empirical constant factor (~N^2 / 24). Artificial Sort provides an intuitive pedagogical paradigm and a dependable, crash-proof sorting primitive for memory-constrained microcontroller architectures.