iDevji

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 lists of 5 elements each

A1 = [9, 5, 8, 3, 6]

and
A2 = [7, 4, 0, 2, 5]

each list will require 52 = 25 units of time which is only half of original 100. But the problem is that if we again concatenate the sorted lists the resultant list still remains unsorted :

A' = [3, 5, 6, 8, 9, 0, 2, 4, 5, 7]

Even if we could not sort the list as whole reducing time complexity is certainly interesting! This property can be used in recursively sorting the array more efficiently. Merge-sort is one such algorithm with O (n log n) time complexity. Merge sort does not concatenate divided list but as the name suggests it merges them. Merging two sorted lists is easy. Another example is selection algorithms where the problem is to find kth smallest/largest elements in a list. Selection also requires sorting. Median of medians is a selection algorithm which uses this property to look for kth smallest/largest element by reducing search space into half at each iteration. Both these algorithms are examples of divide and conquer strategy.