exercises java datastructures net merge-sort in this sectionwe present sorting techniquecalled merge-sortwhich can be described in simple and compact way using recursion divide-and-conquer merge-sort is based on an algorithmic design pattern called divide-and-conquer 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 recurrecursively solve the subproblems associated with the subsets conquertake the solutions to the subproblems and "mergethem into solution to the original problem using divide-and-conquer for sorting recall that in sorting problem we are given sequence of objectsstored in linked list or an arraytogether with some comparator defining total order on these objectsand we are asked to produce an ordered representation of these objects to allow for sorting of either representationwe will describe our sorting algorithm at high level for sequences and explain the details needed to implement it for linked lists and arrays to sort sequence with elements using the three divide-and-conquer stepsthe merge-sort algorithm proceeds as follows divide:if 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