Data structure

(15%) Answer the following questions about external sorting with a computer which is capable of sorting 3 records. (a) Given records with keys 22, 5, 24, 18, 12, 7, 20, 31, 27, 29, 25, 14, 16, 19 initially stored on disk in that order. Conduct an initial scan through all records and partition the records into runs of records that are already in order (similar to the natural merge sort). Show the resulting runs. (b) Use the Huffman Code algorithm to determine the optimal merge order. Show the resulting merge tree and the weighted external path length. (C) Let to, tis, and ntm be defined as in class note except that tis is the time to sort 3 records. Estimate the computing time of the external sort of the resulting merge tree in (b) using tio, tis, and ntm. (15%) Answer the following questions about external sorting with a computer which is capable of sorting 3 records. (a) Given records with keys 22, 5, 24, 18, 12, 7, 20, 31, 27, 29, 25, 14, 16, 19 initially stored on disk in that order. Conduct an initial scan through all records and partition the records into runs of records that are already in order (similar to the natural merge sort). Show the resulting runs. (b) Use the Huffman Code algorithm to determine the optimal merge order. Show the resulting merge tree and the weighted external path length. (C) Let to, tis, and ntm be defined as in class note except that tis is the time to sort 3 records. Estimate the computing time of the external sort of the resulting merge tree in (b) using tio, tis, and ntm