Skip to content

Backward [mp]

Micro pattern

Description

Traverse from the end when dependencies flow toward earlier positions or forward writes would overwrite unread information.

Problems

Avoid overwriting unread values

Write results from the back when the destination overlaps an input.

Process least-significant positions first

Start at the rightmost digit when carry moves toward more significant positions.

Accumulate suffix state

Traverse right to left while maintaining information about later positions.

Preserve stable ordering

Traverse records from right to left when cumulative counts determine their output positions.

Descending buckets or reversed partitions

Consume groups from high to low when larger values must be emitted first.