Merge Sort with list

• O(n log n)
• divide-and-conquer algorithm that divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce a sorted array.

def merge_sort(arr):
    if len(arr) > 1:
        
        # Finding the mid of the array
        mid = len(arr) // 2
        
        # Dividing the elements into 2 halves
        left_half = arr[:mid]
        right_half = arr[mid:]
        
        # Recursive call on each half
        merge_sort(left_half)
        merge_sort(right_half)
        
        # Merge the two halves into sorted order
        i = j = k = 0
        
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        
        # Checking if any element was left
        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

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)

print("Sorted array:", arr)

Step 1: We define a function merge_sort that takes an input list arr.

Step 2: The function first checks if the length of arr is greater than 1, indicating there are elements to sort.

Step 3: It calculates the middle index mid of the array and divides arr into two halves: left_half and right_half.

Step 4: The function recursively calls merge_sort on each half until the base case (single element or empty array) is reached.

Step 5: After sorting both halves, the merge function merges the two sorted halves back into the original array arr.

Step 6: The merge process compares elements from left_half and right_half, placing them in sorted order into arr.

5. Quick Sort:

• O(n log n)
• divide-and-conquer algorithm that uses a pivot element to partition the array into smaller sub-arrays.

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    
    pivot = arr[len(arr) // 2]  # Choosing the middle element as the pivot
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    return quick_sort(left) + middle + quick_sort(right)

# Example usage:
arr = [12, 11, 13, 5, 6, 7]
sorted_arr = quick_sort(arr)

print("Sorted array:", sorted_arr)

Step 1: We define a function quick_sort that takes an input list arr. Step 2: If the length of arr is 1 or less, it simply returns arr (base case for recursion). Step 3: he pivot element is chosen as arr[len(arr) // 2], which is the middle element in this implementation. Step 4: We create three sub-lists (left, middle, and right) using list comprehensions:

• left contains elements less than the pivot.
• middle contains elements equal to the pivot.
• right contains elements greater than the pivot. Step 5: We recursively apply quick_sort to left and right sub-lists and concatenate them along with the middle list to get the sorted array.