Reference no: EM131570736

Question: Prove that the merge sort algorithm is correct. The quick sort is an efficient algorithm. To sort a₁, a₂,...,a_n, this algorithm begins by taking the first element a1 and forming two sublists, the first containing those elements that are less than a1, in the order they arise, and the second containing those elements greater than a1, in the order they arise. Then a1 is put at the end of the first sublist. This procedure is repeated recursively for each sublist, until all sublists contain one item. The ordered list of n items is obtained by combining the sublists of one item in the order they occur.