I am trying to analyze a sorting algorithm that uses an alternating sorting pattern across three piles (Pile A, Pile B, Pile C). I want to see how this pre-sorting rule affects the balance and solvability of a partition problem.

The Algorithm Step-by-Step: Let S be a collection of 3N items with positive integer weights.

1. The Pre-Sorting Sieve: For each step i from 1 to N, take the next 3 items from S and sort them by weight: Large, Medium, and Small.
   • If i is even: Add Large to Pile_A, Small to Pile_B, and Medium to Pile_C.
   • If i is odd: Add Small to Pile_A, Large to Pile_B, and Medium to Pile_C.
2. The Partition Search: After all items are sorted, we look for an exact matching partition. We want to find a way to split the Medium items in Pile_C into two sub-piles, C_to_A and C_to_B, such that:
   • Every single element of Pile_C is placed exactly once into either C_to_A or C_to_B.
   • The Target Equation: Sum(Pile_A) + Sum(C_to_A) == Sum(Pile_B) + Sum(C_to_B) If a matching split is found, the program outputs "yes" and halts.

My Questions for the Board:

1. Imbalance Bounds: Because the algorithm alternates assigning Large and Small items between Pile A and Pile B, the initial difference between their sums, |Sum(Pile_A) - Sum(Pile_B)|, stays highly constrained. If the initial item weights are randomly chosen from a uniform distribution, how do we write a formula for the expected variance of this difference as N grows?
2. Phase Transition and Density: While it is easy to construct worst-case inputs where a perfect partition is completely impossible, what happens under typical conditions? Since Pile C accumulates N median elements (a linear capacity of O(N)) while the initial imbalance between A and B is tightly bound, does this system undergo a sharp statistical phase transition where a valid partition becomes almost certain for dense, random inputs as N approaches infinity?

I would love to see any formulas, recursive relationships, or references to similar 3-pile sorting partition problems! Thanks for any help.