Necessary algorithm for interview | graphic merging and sorting (Python)

Merge sort

The idea of merging and sorting

​ Merge sort mainly uses the divide and conquer strategy to sort , Merge sort is divided into two parts: split and merge . When splitting, we need to recursively perform the operation of dividing the list into two ( Until it is split into only one element in each list ), When merging, we also use the recursive method , Constantly compare the sizes of the elements in the list and merge them according to the size order ( Until merged into a list ).

Graphic merge sort

​ First, we continuously split the whole list ( Take it apart from the middle every time ):

 Insert picture description here

​ The next step is to merge the completely disassembled list , When merging, compare the size of elements and exchange positions ( Every recursion is like this ):

 Insert picture description here

​ The complete consolidation process is as follows :

 Insert picture description here

Nature of merge sort

  • Optimal time complexity : O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
  • Worst time complexity : O ( n l o g 2 n ) O(nlog_2n) O(nlog2n)
  • stability : Stable

Merge sort code implementation

# Merge sort 
lst = list(map(int, input().split(',')))
def mergeSort(alist):
if len(alist) > 1:
mid = len(alist) // 2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i = 0
j = 0
k = 0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k] = lefthalf[i]
i = i + 1
else:
alist[k] = righthalf[j]
j = j + 1
k = k + 1
while i < len(lefthalf):
alist[k] = lefthalf[i]
i = i + 1
k = k + 1
while j < len(righthalf):
alist[k] = righthalf[j]
j = j + 1
k = k + 1
return alist
mergeSort(lst)
Please bring the original link to reprint ,thank
Similar articles