Skip to main content

Merge and radix sort on 142, 523, ...

Short answer

Merge sort: recursive division, then merge steps produce 123,142,144,198,228,249,375,462,523. Radix sort: 3 passes: after units: 142,462,523,123,144,375,228,198,249; after tens: 523,123,228,142,144,249,462,375,198; after hundreds (leading zeros for 2-digit numbers): 123,142,144,198,228,249,375,462,523.

Trace the sorting steps in merge sort and radix sort for sorting the data 142, 523, 228, 375, 462, 198, 249, 144, 123 in ascending order.

Merge sort on 142, 523, 228, 375, 462, 198, 249, 144, 123

Split (left half gets the extra element):

142 523 228 375 462 | 198 249 144 123
142 523 228 | 375 462 | 198 249 | 144 123
142 523 | 228 | 375 | 462 | 198 | 249 | 144 | 123
142 | 523

Merge:

StepMergeResult
1[142] + [523][142, 523]
2[142, 523] + [228][142, 228, 523]
3[375] + [462][375, 462]
4[142, 228, 523] + [375, 462][142, 228, 375, 462, 523]
5[198] + [249][198, 249]
6[144] + [123][123, 144]
7[198, 249] + [123, 144][123, 144, 198, 249]
8[142, 228, 375, 462, 523] + [123, 144, 198, 249][123, 142, 144, 198, 228, 249, 375, 462, 523]

Radix sort on the same data (3 digits, so 3 passes)

Pass 1 (units digit)

Queue0123456789
Keys142, 462523, 123144375228, 198249

List: 142, 462, 523, 123, 144, 375, 228, 198, 249

Pass 2 (tens digit)

Queue0123456789
Keys523, 123, 228142, 144, 249462375198

List: 523, 123, 228, 142, 144, 249, 462, 375, 198

Pass 3 (hundreds digit)

Queue0123456-9
Keys123, 142, 144, 198228, 249375462523

Answer: 123, 142, 144, 198, 228, 249, 375, 462, 523

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 7 questions →