merge-sort divide-and-conquer the first two algorithms we describe in this merge-sort and quick-sortuse recursion in an algorithmic design pattern called divide-and-conquer we have already seen the power of recursion in describing algorithms in an elegant manner (see the divide-and-conquer pattern consists of the following three steps divideif the input size is smaller than certain threshold (sayone or two elements)solve the problem directly using straightforward method and return the solution so obtained otherwisedivide the input data into two or more disjoint subsets conquerrecursively solve the subproblems associated with the subsets combinetake the solutions to the subproblems and merge them into solution to the original problem using divide-and-conquer for sorting we will first describe the merge-sort algorithm at high levelwithout focusing on whether the data is an array-based (pythonlist or linked listwe will soon give concrete implementations for each to sort sequence with elements using the three divide-and-conquer stepsthe merge-sort algorithm proceeds as follows divideif has zero or one elementreturn immediatelyit is already sorted otherwise ( has at least two elements)remove all the elements from and put them into two sequencess and each containing about half of the elements of sthat iss contains the first  / elements of sand contains the remaining / elements conquerrecursively sort sequences and combineput back the elements into by merging the sorted sequences and into sorted sequence in reference to the divide stepwe recall that the notation xindicates the floor of xthat isthe largest integer ksuch that < similarlythe notation xindicates the ceiling of xthat isthe smallest integer msuch that <