Searching and sorting are two basic problems which occur in various more complex computing problems. Time complexity of sorting algorithms cannot get better than O (nlogn). Many popular algorithms have polynomial time complexity O (n2). Undoubtedly sorted lists are interesting because we can solve many problems using it: from binary search to Kruskal's algorithm. This post tries to point out why sorting divisions of lists (say, two halves) is interesting using examples of merge sort and selection algorithms.
If we have a list of unsorted numbers : A= [9, 5, 8, 3, 6, 7, 4, 0, 2, 5] sorting it using any O(n2) sorting algorithm requires 102 = 100 units of time. If we divide the list into two l