merge sorted files this problem is motivated by the following scenario you are given fileseach containing stock trade information for an & company each trade is encoded by line in the following format ,aapl, , the first number is the time of the trade expressed as the number of milliseconds since the start of the day' trading lines within each file are sorted in increasing order of time the remaining values are the stock symbolnumber of sharesand price you are to create single file containing all the trades from the filessorted in order of increasing trade times the individual files are of the order of - megabytesthe combined file will be of the order of five gigabytes in the abstractwe are trying to solve the following problem write program that takes as input set of sorted sequences and computes the union of these sequences as sorted sequence for exampleif the input is ih iand ithen the output is hintwhich part of each sequence is significant as the algorithm executessolutiona brute-force approach is to concatenate these sequences into single array and then sort it the time complexity is ( log )assuming there are elements in total the brute-force approach does not use the fact that the individual sequences are sorted we can take advantage of this fact by restricting our attention to the first remaining element in each sequence specificallywe repeatedly pick the smallest element amongst the first element of each of the remaining part of each of the sequences min-heap is ideal for maintaining collection of elements when we need to add arbitrary values and extract the smallest element for ease of expositionwe show how to merge sorted arraysrather than files as concrete examplesuppose there are three sorted arrays to be mergedh ih iand for simplicitywe show the min-heap as containing entries from these three arrays in practicewe need additional information for each entrynamely the array it is fromand its index in that array (in the file case we do not need to explicitly maintain an index for next unprocessed element in each sequence--the file / library tracks the first unread entry in the file the min-heap is initialized to the first entry of each arrayi it is { we extract the smallest entry and add it to the output which is then we add to the min-heap which is { now (we chose the entry corresponding to the third array arbitrarilyit would be perfectly acceptable to choose from the second array nextextract and add it to the output which is ithen add to the min-heap which is { nextextract and add it to the output which is ithen add to the min-heap which is { nextextract and add it to the output which is ithen add to the min-heap which is { nextextract and add it to the output which is iassuming is selected from the second arraywhich has no remaining elementsthe min-heap is { nextextract and add it to the output which is ithen add to the min-heap which is { nextextract and add it to the output which is ithe min-heap is { nextextract and add it to the output which is inowall elements are processed and the output stores the sorted elements def merge_sorted_arrays sorted_arrays )min_heap [builds list of iterators for each array in sorted_arrays sorted_arrays_iters [iter(xfor in sorted_arrays