def mergeSort(arr, key):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        mergeSort(left_half, key)
        mergeSort(right_half, key)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):
            if left_half[i].get(key) < right_half[j].get(key):
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1

        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1

Eli_list = [
    {"name": "Bob", "age": 25, "city": "London"},
    {"name": "Khalid", "age": 32, "city": "New York"},
    {"name": "Eli", "age": 19, "city": "Paris"},
    {"name": "David", "age": 41, "city": "Tokyo"},
    {"name": "Eve", "age": 28, "city": "Berlin"}
]

print("Original List:")
print(Eli_list)

import time

def bubbleSort(arr, key):
    n = len(arr)
    for i in range(n - 1):
        for j in range(0, n - i - 1):
            if arr[j][key] > arr[j + 1][key]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

Eli_list = [
   {"name": "Bob", "age": 25, "city": "London"},
    {"name": "Khalid", "age": 32, "city": "New York"},
    {"name": "Eli", "age": 19, "city": "Paris"},
    {"name": "David", "age": 41, "city": "Tokyo"},
    {"name": "Eve", "age": 28, "city": "Berlin"}
]

print("\nBubble Sort:")
start_time = time.time()
for key in Eli_list[0]:
    bubbleSort(Eli_list, key)
    print(f"\nSorted by '{key}':")
    print(Eli_list)
end_time = time.time()
bubble_sort_time = end_time - start_time
print("Bubble Sort Time:", bubble_sort_time)

import time

print("\nMerge Sort:")
start_time = time.time()
for key in Eli_list[0]:
    mergeSort(Eli_list, key)
    print(f"\nSorted by '{key}':")
    print(Eli_list)
end_time = time.time()
merge_sort_time = end_time - start_time
print("Merge Sort Time:", merge_sort_time)

print("\nSorting Analysis:")
print(f"Number of elements: {len(Eli_list)}")
print(f"Bubble Sort Comparisons: {len(Eli_list) * (len(Eli_list) - 1) // 2}")
print(f"Bubble Sort Swaps: {len(Eli_list) * (len(Eli_list) - 1) // 2}")
print(f"Bubble Sort Time: {bubble_sort_time} seconds")
print(f"Merge Sort Comparisons: {len(Eli_list) * (len(Eli_list) - 1) // 2}")
print(f"Merge Sort Swaps: {len(Eli_list) * (len(Eli_list) - 1) // 2}")
print(f"Merge Sort Time: {merge_sort_time} seconds")