87 lines
2.1 KiB
Python
87 lines
2.1 KiB
Python
"""
|
|
Merge Sort
|
|
|
|
by BBaoVanC
|
|
|
|
This import uses the merge method of sorting.
|
|
Pros:
|
|
Time doesn't increase as fast as insertion when you add more numbers.
|
|
Cons:
|
|
Not the most efficient for small lists
|
|
"""
|
|
|
|
|
|
def sort(A):
|
|
def merge(A, p, q, r):
|
|
# print(A)
|
|
n1 = q - p
|
|
# print("n1: " + str(n1))
|
|
n2 = r - q - 1
|
|
# print("n2: " + str(n2))
|
|
L = []
|
|
R = []
|
|
for num in range(0, n1 + 2):
|
|
L.append(0)
|
|
for num in range(0, n2 + 2):
|
|
R.append(0)
|
|
for i in range(0, n1 + 1):
|
|
# print("i: " + str(i))
|
|
# print("p + i: " + str(p + i))
|
|
L[i] = A[p + i]
|
|
for j in range(0, n2 + 1):
|
|
R[j] = A[q + j + 1]
|
|
# print("n1: " + str(n1))
|
|
# print("n2: " + str(n2))
|
|
L[n1 + 1] = float('inf')
|
|
R[n2 + 1] = float('inf')
|
|
i = 0
|
|
j = 0
|
|
for k in range(p, r + 1):
|
|
if L[i] <= R[j]:
|
|
A[k] = L[i]
|
|
i += 1
|
|
else:
|
|
A[k] = R[j]
|
|
j += 1
|
|
|
|
return A
|
|
|
|
def merge_sort(A, p, r):
|
|
if p < r:
|
|
q = int(((p + r + 1) / 2) - 1)
|
|
A = merge_sort(A, p, q)
|
|
A = merge_sort(A, q + 1, r)
|
|
A = merge(A, p, q, r)
|
|
return A
|
|
|
|
A = merge_sort(A, 0, len(A) - 1)
|
|
return A
|
|
|
|
|
|
if __name__ == '__main__':
|
|
from timeit import default_timer as timer
|
|
|
|
with open("nums.txt") as f:
|
|
A = f.readlines()
|
|
A = [x.strip() for x in A]
|
|
A = [int(x) for x in A]
|
|
|
|
start = timer()
|
|
sorted_a = sort(A)
|
|
elapsed_time = timer() - start
|
|
print("TIME: %.16f" % elapsed_time)
|
|
|
|
# print("Opening file")
|
|
f = open("sort_merge.txt", "w+")
|
|
nums2 = list()
|
|
for item in sorted_a:
|
|
item = str(item) + "\n" # add newline character to each item in the nums2 list...
|
|
nums2.append(item) # ...
|
|
nums2[-1] = nums2[-1].strip() # remove newline character from last item in list
|
|
for item in nums2:
|
|
# print("Writing number: " + item)
|
|
f.write(item) # write each number to the file
|
|
# print("Closing file")
|
|
f.close()
|
|
# print("FINISHED")
|