Notes

I am going to have two functions. The first one is to handle the recursive splitting of the array into smaller parts, and the second one will handle merging those parts back together in sorted order.

The first function is the main merge_sort function. Its job is to recursively divide the input array into smaller parts until each part contains only one element or no elements.

The second function is called merge, and its purpose is to take two sorted arrays and combine them into a single sorted array

def merge_sort(arr):
    if len(arr) <= 1:
        return arr  # Base case: array with 0 or 1 elements is already sorted

    # Split the array into two halves
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])

    # Merge the sorted halves
    return merge(left, right)

def merge(left, right):
    sorted_array = []
    i = j = 0

    # Compare elements from left and right and merge them in sorted order
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            sorted_array.append(left[i])
            i += 1
        else:
            sorted_array.append(right[j])
            j += 1

    # Add any remaining elements from left or right
    sorted_array.extend(left[i:])
    sorted_array.extend(right[j:])

    return sorted_array

# Example Usage
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Sorted Array:", sorted_arr)

Time Complexity.
Best Case, Worst Case, and Average Case: O(nlogn)
Divide Step:

    The array is repeatedly divided into two halves until we reach arrays of size 1.
    The number of divisions is equal to the height of the recursion tree, which is log_2(n).
Merge Step:
    Each level of the recursion tree processes 𝑛 elements during merging.
    At each level, the merging of two halves requires O(n) time.

Total Work:
The total work across all levels of the recursion tree is:

O(n)+O(n)+... + O(n) (for log2(n) levels) =  O(nlogn)

Key Insight: The log 𝑛 factor comes from the depth of the recursion (splitting), and the 𝑛 factor comes from merging at each level.

Space Complexity.
O(n)
Why?

The algorithm requires additional space for the temporary arrays used during the merge step.
At any given time, we store a portion of the array in temporary arrays for merging, which can take up to O(n) space

Recursion Stack Space: 𝑂(log𝑛)
The recursion depth corresponds to the height of the recursion tree, which is log2(n)

total = log2(n) + O(n) = O(n)

21. Merge Two Sorted Lists

def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode()
    cur = dummy

    while list1 and list2:
        if list1.val < list2.val:
            cur.next = list1
            list1 = list1.next
        else:
            cur.next = list2
            list2 = list2.next
        cur = cur.next
    if list1:
        cur.next = list1
    if list2:
        cur.next = list2
    return dummy.next

# O(m+n)
# O(1)

23. Merge k Sorted Lists

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        '''
        1. implement mergeTwoLists
        2. will divide and conquar method with mergeTwoLists
        '''
        if not lists:
            return None

        if len(lists) == 1:
            return lists[0]

        mid = len(lists) // 2 
        left = self.mergeKLists(lists[:mid])
        right = self.mergeKLists(lists[mid:])

        return self.mergeTwoLists(left, right)

    def mergeTwoLists(self, list1, list2):
        dummy = ListNode()
        cur = dummy

        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next

        if list1:
            cur.next = list1
        elif list2:
            cur.next = list2
        return dummy.next

# N: Total number of nodes across all linked lists.
# k: Number of linked lists.
#The algorithm splits the 𝑘 lists into two halves repeatedly until only one list remains.
# This takes log 𝑘 levels of merging.        

# At each level of merging, all 𝑁 nodes are processed across all pairs of lists.

#Space

# The algorithm divides the list recursively into two halves.
# At each recursive call, the depth of the recursion increases by 1.
# For 𝑘 lists, the depth of recursion is log 𝑘.