"""
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")