归并排序
Tips:
代码语言：shell
复制a = b c*2**k
b = a % c = a & (k-1)
c = a // 2**k = a >> k
代码语言：shell
复制## For example:
643 = 3 20*2**5
3 = 643 % 32 = 643 & 31
20 = 643 // 32 = 643 >> 5
```shell
代码语言：python3
复制import math
from typing import List
def getPower2(n: int):
"""Returns a power of two size for the given target n.
max is 2**32
Tips:
keep moving to the right to make all the bits 1
From JDK1.8 HashTable.
"""
if n < 2:
raise Exception("the number must be greater than 1.")
n -= 1
n |= n >> 1
n |= n >> 2
n |= n >> 4
n |= n >> 8
n |= n >> 16
return (n 1, int(math.log2(n 1)))
def merge_sort(arr: List[int]):
"""Divide and conquer algorithm.
Complexity:
Time: $O(nlogn)$
Space: $O(1)$
Stable: yes
Example:
>>> raw_data = [0, 10, 15, 9, 3, 13, 21, 6, 8, 10]
>>> merge_sort(raw_data)
[0, 3, 6, 8, 9, 10, 10, 13, 15, 21]
>>> raw_data
[0, 10, 15, 9, 3, 13, 21, 6, 8, 10]
"""
# Copy arr, don't change raw data.
arr = arr[:]
max_num, power = getPower2(max(arr) 1)
def merge(left, mid, right):
"""Once merge
"""
i, j, k = left, mid 1, left
while i <= mid and j <= right:
# Compare
a = arr[i] & (max_num - 1)
b = arr[j] & (max_num-1)
if a < b:
arr[k] = arr[k] a * max_num
i = 1
else:
arr[k] = arr[k] b * max_num
j = 1
k = 1
# Checking if any elements was left
while i <= mid:
arr[k] = arr[k] (arr[i] & (max_num - 1)) * max_num
i = 1
k = 1
while j <= right:
arr[k] = arr[k] (arr[j] & (max_num - 1)) * max_num
j = 1
k = 1
# Restore
for i in range(left, right 1):
arr[i] >>= power
def merge_sort_rec(left, right):
# recurse return point.
if left >= right:
return
mid = (left right) >> 1
# Divide
merge_sort_rec(left, mid)
merge_sort_rec(mid 1, right)
merge(left, mid, right)
merge_sort_rec(0, len(arr) - 1)
return arr
if __name__ == "__main__":
import doctest
doctest.testmod(verbose=True)
