Subsumption sorting is a typical application of the partitioning method
Idea: first recursively decompose the array, then merge the arrays
Principle: the array will be decomposed after the smallest, and then merge the two ordered arrays, the basic idea is to compare the two arrays of the top of the number, who is small, who will be taken, after taking, the corresponding pointer back thought. Then compare again, until an array is empty, and finally copy the remaining part of the other array over.
Python code implementation:
#Backsummer Sort def merge_sort(alist): if len(alist) <= 1: return alist # Dichotomous decomposition num = len(alist) / 2 left = merge_sort(alist[:num]) right = merge_sort(alist[num:]) # Merge return merge(left, right) def merge(left, right): '''Merge operation to combine two ordered arrays left[] and right[] into one large ordered array''' # Left and right subscript pointers l, r = 0, 0 result = [] while l < len(left) and r < len(right): if left[l] < right[r]: (left[l]) l += 1 else: (right[r]) r += 1 result += left[l:] result += right[r:] return result alist = [54, 26, 93, 17, 77, 31, 44, 55, 20] sorted_alist = merge_sort(alist) print(sorted_alist)
Time Complexity:
Optimal time complexity: O(nlongn)
Worst time complexity : O(nlongn)
Stability: Stable
This is the whole content of this article.