How to implement merge sort of python sorting algorithm

Algorithm Description

The first advanced sorting algorithm in this section is merge sort. The word "merger" means "to merge". As the name suggests, the merge sort algorithm is an algorithm that first splits the sequence into sub-sequences, sorts the sub-sequences, and then merges the ordered sub-sequences into a complete ordered sequence. It actually adopted the idea of ​​divide and conquer.

The average time complexity of merge sort is O(nlgn), the time complexity in the best case is O(nlgn), and the time complexity in the worst case is also O(nlgn). Its space complexity is O(1). In addition, merge sort is a stable sorting algorithm.

Taking ascending sorting as an example, the process of the merge algorithm is shown in Figure 2-21.

The original array is an unordered array of 8 numbers. After one operation, the array of 8 numbers is divided into two unordered arrays of 4 numbers. Each operation splits the unordered array in half until all smallest subarrays contain only one element. When there is only one element in the array, the array must be ordered. Then, the program starts to merge every two small ordered arrays into a large ordered array. First, merge two arrays containing one number into an array containing two numbers, then merge two arrays containing two numbers into an array containing four numbers, and finally merge them into an array containing eight numbers. array. When all ordered arrays are combined, the longest ordered array formed is sorted.

Code implementation

Merge sort code:

  #归并排序
nums = [5,3,6,4,1,2,8,7]
def MergeSort(num):
  if(len(num)<=1):　　　　　　　　#递归边界条件
   return num　　　　　　　　　#到达边界时返回当前的子数组
  mid = int(len(num)/2)　　　　　 #求出数组的中位数
  llist,rlist = MergeSort(num[:mid]),MergeSort(num[mid:])#调用函数分别为左右数组排序
  result = []
  i,j = 0,0
  while i < len(llist) and j < len(rlist): #while循环用于合并两个有序数组
   if rlist[j]<llist[i]:
     result.append(rlist[j])
     j += 1
   else:
     result.append(llist[i])
     i += 1
  result += llist[i:]+rlist[j:]　 #把数组未添加的部分加到结果数组末尾
  return result　　　　　　　　　#返回已排序的数组
print(MergeSort(nums))

Run the program, the output result is:

[1,2,3,4,5,6,7,8]

In MergeSort In the () function, the first step is to judge the boundary conditions. When an array containing only one element is passed as a function parameter, the element alone exists in the array, so the array has reached its minimum size. Once you are done with the task of recursively decomposing an array, just return the decomposed array to the previous level of recursion.

If the length of the unsorted array is still greater than 1, then use the variable mid to store the middle subscript of the array and divide the unsorted array into two subarrays on the left and right. Then, create two new arrays to store the sorted left and right subarrays. The idea of ​​recursion is used here. We only think of the MergeSort() function as a function that sorts a list, although inside the MergeSort() function, the function itself can also be called to sort two subarrays.

Subsequently, use a while loop to merge the two already sorted arrays. Since the relative size of the elements in the two arrays cannot be determined, we use two variables, i and j, to mark the positions of the elements waiting to be added in the left sub-array and right sub-array respectively. When the while loop ends, there may be some largest elements remaining at the end of a subarray that have not been added to the result list, so the result =llist[i:] rlist[j:] statement is to prevent these elements from being missed. After the array merging is completed, the function outputs an ordered array.

The above is the detailed content of How to implement merge sort of python sorting algorithm. For more information, please follow other related articles on the PHP Chinese website!