merge-sort on sequence of size has height log we leave the justification of proposition as simple exercise ( - we will use this proposition to analyze the running time of the merge-sort algorithm having given an overview of merge-sort and an illustration of how it workslet us consider each of the steps of this divide-and-conquer algorithm in more detail the divide and recur steps of the merge-sort algorithm are simpledividing sequence of size involves separating it at the element with index / and the recursive calls simply involve passing these smaller sequences as parameters the difficult step is the conquer stepwhich merges two sorted sequences into single sorted sequence thusbefore we present our analysis of merge-sortwe need to say more about how this is done merging arrays and lists to merge two sorted sequencesit is helpful to know if they are implemented as arrays or lists thuswe give detailed pseudo-code describing how to merge two sorted sequences represented as arrays and as linked lists in this section merging two sorted arrays