recursion , , while *logn is only , if sorting this many items required seconds with the mergesortit would take almost hours for the insertion sort the mergesort is also fairly easy to implement it' conceptually easier than quicksort and the shell shortwhich we'll encounter in the next the downside of the mergesort is that it requires an additional array in memoryequal in size to the one being sorted if your original array barely fits in memorythe mergesort won' work howeverif you have enough spaceit' good choice merging two sorted arrays the heart of the mergesort algorithm is the merging of two already-sorted arrays merging two sorted arrays and creates third arraycthat contains all the elements of and balso arranged in sorted order we'll examine the merging process firstlater we'll see how it' used in sorting imagine two sorted arrays they don' need to be the same size let' say array has elements and array has they will be merged into an array that starts with empty cells figure shows these arrays abefore merge bafter merge figure merging two arrays in the figurethe circled numbers indicate the order in which elements are transferred from and to table shows the comparisons necessary to determine which element will be copied the steps in the table correspond to the steps in the figure following each comparisonthe smaller element is copied to