Analysis of Algorithms : An Active Learning Approach

268 APPENDIX C

Merge Sort

Pass 6: 1 0897652413111213141516

Pass 7:98576324110111213141516

Pass 8:87546321910111213141516

Pass 9:76541328910111213141516

Pass 10:64521378910111213141516

Pass 11:54321678910111213141516

Pass 12:42315678910111213141516

Pass 13:32145678910111213141516

Pass 14:21345678910111213141516

Pass 15:12345678910111213141516

The Original List:62471385

After merging location 1 to location 2:26471385

After merging location 3 to location 4:26471385

After merging location 1 to location 4:24671385

After merging location 5 to location 6:24671385

After merging location 7 to location 8:24671358

After merging location 5 to location 8:24671358

After merging location 1 to location 8:12345678

The Original List: 15 4 1 0869161731114251213

After merging loca-

tion 1 to location 2: 4 15 1 0869161731114251213

After merging loca-

tion 3 to location 4: 4 15 8 10 6 9 1 61731114251213

After merging loca-

tion 1 to location 4: 4 8 10 15 6 9 1 61731114251213

After merging loca-

tion 5 to location 6: 4 8 10 15 6 9 1 61731114251213

After merging loca-

tion 7 to location 8: 4 8 10 1 569116731114251213

After merging loca-

tion 5 to location 8: 4 8 10 1 516916731114251213

After merging loca-

tion 1 to location 8:14689101516731114251213