- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 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
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
"""
This module provides a function merge_sort, which is one of the simplest and the
most robust sorting algorithms, being relatively fast, having (n*log(n))
complexity. Also, this module counts the number of inversions in a given array.
Usage: import this module and use the function merge_sort. The first element in
a returned tuple shall be a sorted array, while the second one will be a number
of inversions in the array.
Copyright (C) 2021 Sergay Gayorgyevich.
This program is free software: you can redistribute it and/or modify
it under the terms of the GNU Affero General Public License as
published by the Free Software Foundation, either version 3 of the
License, or (at your option) any later version.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU Affero General Public License for more details.
You should have received a copy of the GNU Affero General Public License
along with this program. If not, see <https://www.gnu.org/licenses/>.
"""
import argparse
def merge_sort(array : list) -> (list, int):
"""
MergeSort algorithm with additional inversion counting.
input: array.
output: sorted array and number of inversions in it.
"""
if len(array) <= 1:
return (array, 0)
elif len(array) == 2:
if array[0] > array[1]:
array[0], array[1] = array[1], array[0]
return (array, 1)
return (array, 0)
mid = len(array) // 2
left, left_inversions = merge_sort(array[:mid])
right, right_inversions = merge_sort(array[mid:])
merged, split_inversions = _merge(left, right)
return (merged, right_inversions + left_inversions + split_inversions)
def _merge(left_array : list, right_array : list) -> (list, int):
"""
This function isn't supposed to be called, it's an inner function of the
module, and not a part of its API!
The purpose of this function is to merge two arrays. Due to the nature of
the MergeSort algorithm, it operates two arrays, both of which are sorted.
input: two sotrted arrays.
output: sorted array, consisting of elements of both operated arrays.
"""
resulting_array = list()
inversion_count = 0
c_len = len(left_array) + len(right_array)
for i in range(c_len):
if (len(left_array) != 0) and (len(right_array) != 0):
if left_array[0] > right_array[0]:
inversion_count += len(left_array)
resulting_array.append(right_array.pop(0))
else:
resulting_array.append(left_array.pop(0))
elif len(left_array) == 0:
resulting_array.append(right_array.pop(0))
elif len(right_array) == 0:
resulting_array.append(left_array.pop(0))
return (resulting_array[:], inversion_count)
# For testing purposes only! Do not use in production!
if __name__ == '__main__':
DESC = "Sort an array and print an amount of inversions it has." # Description for argparse.
argparser = argparse.ArgumentParser(description = DESC)
argparser.add_argument("elements", type = int, nargs = '+', help = "A list to be sorted.")
args = argparser.parse_args()
print(merge_sort(args.elements))
Follow us!