[Enhancement]: Integrate k-way merge, SSB, and segmented-radix paths for LRB large segments #12468

Area

CUB

Problem

The bounded GroupMerge backend queues oversized segments but needs complete overflow sorting before it can be selected for general eligible public calls. Large-segment strategies should be integrated behind that overflow contract rather than delaying correctness until every optimization is available.

Proposed work

• Track three large-segment routes: k-way merge, SSB, and CUB's existing segmented-radix sorting path.
• Confirm the implementation source, supported types/modes, scratch needs, and synchronization contract for each route, including SSB.
• First provide a correct baseline by consuming overflow IDs with the existing CUB segmented-radix agent; use a new public DeviceSegmentedRadixSort invocation only if justified by the integration.
• Integrate and benchmark the k-way merge and SSB candidates, then choose tunable routing thresholds based on measured workloads.
• Coordinate bounded/overflow output placement, temporary storage, direction, and eventual key/value and DoubleBuffer support.

Validation / completion criteria

• Sort mixed bounded/overflow inputs completely, including one huge segment, many large segments, empty overflow, and skewed layouts.
• Compare all three routes on correctness, memory footprint, launch overhead, and latency; measure rather than assume multi-CTA gains.
• Record graph-capture and device-invocation limitations for each route and preserve fallback for unsupported configurations.

Context

Follow-up to the LRB segmented-sort backend in #12236.

Related work: #10806, #10949.