sorting - How do I extract an algorithm from these instructions? -

i've been reading through the art of computer programming, , though has moments of higher maths can't get, exercises have been fun do.

after i've done 1 of them go on answer, see if did better or worse book suggests (usually worse), don't answer current 1 i'm on trying convey @ all.

the book's question , proposed solution can found here

what i've understood t may number of 'missing' elements or may general constant, don't understand seemingly arbitrary instruction sort them based on components, me looks spinning wheels in place since @ first glance doesn't closer original order. , decision (among others) replace 1 part of paired names number ( file g contains pairs (i,xi) n−t < ≤ n).

so question is, simply, how extract algorithm answer?

bit of clarification:

i understand aims do, , how go translating c++. not understand why supposed sort copies of input file, , if criteria sort by, reasons changing 1 side of pairs number.

it's assumed names sortable, , there sufficient number of tape drives solve problem. define pair (name, next_name), next_name name of person west. copy of file of pairs made tape. first file sorted name, second file sorted next_name. tape sorts bottom merge sort or more complex variation called polyphase merge sort, problem, standard bottom merge sort enough. c++, use std::stable_sort() emulate tape sort, using lambda function compare, sorting name first file , sorting next_name second file.

the terminology indexing uses name[1] represent eastern name, , name[n] represent western name.

after initial sorting of 2 files of pairs, solution states "passing on files" done identify next last name, name[n-1], doesn't specify how. in process, assume name[n] identified. files compared in sequence, comparing name first file next_name second file. mismatch indicates either first name, name[1], or last name, name[n], or in vary rare circumstance, both, , next pairs each file have checked determine mismatch indicates. @ time last name, name[n] identified, name second file pair next last name, name[n-1].

once name[n-1] , name[n] known, merge operation using both files performed, skipping name[n-1] , name[n] create f pairs (name[i], name[i+2]) = 1 n-2 (in name order), , g 2 pairs (n-1, x[n-1]), , (n, x[n]), in name order (g , g' in name order until last step).

f copied h, , iterative process performed described in algorithm, t doubling each time, 2, 4, 8, ... . after each pass, f' contains pairs (x[i], x[i+t]) = 1 n-t, g' sorted , merged g g', resulting in g' contains pairs (i, x[i]) = n-t n, in name order. pairs end in g (i, x[i]) = 1 n, in name order, , g sorted index (left part of pair), resulting in names in sorted order.