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 ）： ​ 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 ）： ​ The complete consolidation process is as follows ： Nature of merge sort

• Optimal time complexity ： O ( n l o g 2 n ) O(nlog_2n)
• Worst time complexity ： O ( n l o g 2 n ) O(nlog_2n)
• 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)