Summary

Natural merge sort scans for existing ascending or strictly descending runs. It reverses descending runs and merges adjacent runs until one remains.

How it Works

• Scan the array for maximal ordered runs.

• Reverse strictly descending runs; equal keys stay in input order.

• Merge neighboring runs stably, then repeat.