-
Notifications
You must be signed in to change notification settings - Fork 4
/
merge_sort.py
69 lines (48 loc) · 1.86 KB
/
merge_sort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
import sys
sys.path.append("..")
from utils.file_reader import *
def get_data():
return list(map(lambda s: int(s), read_input(FilePath.INVERSIONS)))
"""
Runs merge sort counting the number of inversions
Given an array splitted in half, consider i, j = 0, N/2. An inversion is counted when i > j.
So the algorithm is divided in three parts:
* Left inversions - when i,j <= N/2
* Right inversions - when i,j > N/2
* Splitted inversions - when i <= N/2 < j
"""
def merge_sort(data):
def split(left, right):
c = []
left_length, right_length = len(left), len(right)
left_index, right_index, invs = 0, 0, 0
for k in range(left_length + right_length):
if left_index < left_length and right_index < right_length:
cur_l, cur_r = left[left_index], right[right_index]
if cur_l <= cur_r:
c.append(cur_l)
left_index += 1
else:
c.append(cur_r)
invs += (left_length - left_index)
right_index += 1
elif not left_index < left_length:
c.append(right[right_index])
right_index += 1
else:
c.append(left[left_index])
left_index += 1
return c, invs
def sort(nums, invs, i, j):
if abs(j - i) == 1:
return [nums[i]], invs
left, invs_left = sort(nums, invs, i, (i + j) // 2)
right, invs_right = sort(nums, invs, (i + j) // 2, j)
c, inv_split = split(left, right)
return c, (invs_left + invs_right + inv_split)
return sort(data, 0, 0, len(data))
def count_inversions(data):
return merge_sort(data)
data = get_data()
numbers, inversions = count_inversions(data)
print('number of inversions = %d' % inversions)