import random
import time
import sys

class ProgressTracker:
    def __init__(self, total_elements):
        self.total_elements = total_elements
        self.processed_elements = 0
        self.bar_width = 50
        
    def update(self, elements_processed):
        self.processed_elements += elements_processed
        self.display_progress()
    
    def display_progress(self):
        if self.total_elements == 0:
            return
            
        progress = self.processed_elements / self.total_elements
        filled_length = int(self.bar_width * progress)
        
        bar = '*' * filled_length + ' ' * (self.bar_width - filled_length)
        percentage = progress * 100
        
        sys.stdout.write(f'\rProgress: [{bar}] {percentage:.1f}%')
        sys.stdout.flush()
    
    def finish(self):
        sys.stdout.write('\n')
        sys.stdout.flush()

def merge_sort(nums, progress_tracker=None):
    length_of_nums = len(nums)
    
    if length_of_nums < 2:
        return nums

    split = int(length_of_nums / 2)    
    
    split_one = nums[0:split]
    split_two = nums[split:]
    
    sorted_left_side = merge_sort(split_one, progress_tracker)
    sorted_right_side = merge_sort(split_two, progress_tracker)
    
    return merge(sorted_left_side, sorted_right_side, progress_tracker)


def merge(first, second, progress_tracker=None):
    final = []
    i = 0
    j = 0

    while i < len(first) and j < len(second):
        if first[i] <= second[j]:
            final.append(first[i])
            i += 1
        else:
            final.append(second[j])
            j += 1
        
    # Add remaining elements
    if len(first) > 0:
        for item in first[i:]:
            final.append(item)
    if len(second) > 0:
        for item in second[j:]:
            final.append(item)
    
    # Update progress tracker with the number of elements merged
    if progress_tracker:
        progress_tracker.update(len(final))
    
    return final

# Create a list of random numbers
list_size = 1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * 9
num_list = [random.randint(1, 99999) for _ in range(list_size)]

print(f"Sorting a list of {list_size} numbers using Merge Sort...")

# Create progress tracker
# For merge sort, we'll track based on merge operations
# The total number of elements processed during merging is approximately n * log(n)
import math
estimated_operations = list_size * math.ceil(math.log2(list_size))
progress_tracker = ProgressTracker(estimated_operations)

# --- Start the timer (using perf_counter for better benchmarking) ---
start_time = time.perf_counter()

# --- Call the sorting function ---
sorted_list = merge_sort(num_list, progress_tracker)

# --- Stop the timer ---
end_time = time.perf_counter()

# Finish the progress bar
progress_tracker.finish()

# --- Calculate and print elapsed time ---
elapsed_time = end_time - start_time
print(f"Elapsed time: {elapsed_time:.4f} seconds")

# --- Optional: Print a small portion of the sorted list to verify ---
print("First 10 elements of sorted list:", sorted_list[:10])
print("Last 10 elements of sorted list:", sorted_list[-10:])