# Sorting

TC: nLog(n)
SC: O(1) for some runtimes O(n) for speedup

Space complexity : O(N) or O(log⁡N)
- The space complexity of the sorting algorithm depends on the implementation of each programming language.
- For instance, the list.sort() function in Python is implemented with the Timsort algorithm whose space complexity is O(N).
- In Java, the Arrays.sort() is implemented as a variant of quicksort algorithm whose space complexity is O(logN).

arr = [1, 30, 2, 4]
arr.sort() # asc , inplace
arr.sort(reverse = True)

arr.sort(key=lambda x: x[1])
arr.sort(key=lambda x: (x[0], x[1]) # sort by multiple keys 

## Problems
- merge two sorted arrays
- Naive Solution: Create new array with size m + n. copy all items in to that array, sort them and print elements in that array.

# TC: O(n + m)
# SC: O(1)
def merge(arr1, arr2):
    i = 0
    j = 0
    m = len(arr1)
    n = len(arr2)
    while i < m and j < n:
        # print(f'{i}/{m},{j}/{n}')
        if arr1[i] <= arr2[j]:
            print(arr1[i], end=' ')
            i += 1
        else:
            print(arr2[j], end=' ')
            j += 1 
    while j < n:
        print(arr2[j], end=' ')
        j += 1 
    while i < m:
        print(arr1[i], end=' ')
        i += 1     
    print()
arr1 = [5, 6, 6, 15]
arr2 = [10, 15, 20]
merge(arr1, arr2)

- intersection of two sorted arrays (skip repeated)

# TC: O(n + m)
# SC: O(1)
def intersection(arr1, arr2):
    i = 0
    j = 0
    m = len(arr1)
    n = len(arr2)
    while i < m and j < n:
        if i > 0 and arr1[i] == arr1[i - 1]:
            i += 1
            continue
        if j > 0 and arr2[j] == arr2[j - 1]:
            j += 1
            continue
        if arr1[i] == arr2[j]:
            print(arr1[i], end=' ')
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            i += 1
        else:
            j += 1
    print()

arr1 = [3, 5, 10, 10, 10, 15, 15, 20]
arr2 = [5, 10, 10, 15, 30]
intersection(arr1, arr2)

- Union of two sorted arrays

# TC: O(n + m)
# SC: O(1)
def union(arr1, arr2):
    i = 0
    j = 0
    m = len(arr1)
    n = len(arr2)
    while i < m and j < n:
        if i > 0 and arr1[i] == arr1[i - 1]:
            i += 1
            continue
        if j > 0 and arr2[j] == arr2[j - 1]:
            j += 1
            continue
        if arr1[i] == arr2[j]:
            print(arr1[i], end=' ')
            i += 1
            j += 1
        elif arr1[i] < arr2[j]:
            print(arr1[i], end=' ')
            i += 1
        else:
            print(arr2[j], end=' ')
            j += 1
    
    while i < m:
        if i > 0 and arr1[i] == arr1[i - 1]:
            i += 1
            continue
        print(arr1[i], end=' ')
        i += 1
    while j < n:
        if j > 0 and arr2[j] == arr2[j - 1]:
            j += 1
            continue
        print(arr2[j], end=' ')
        j += 1
    print()

arr1 = [3, 5, 10, 10, 10, 15, 15, 20]
arr2 = [5, 10, 10, 15, 30]
union(arr1, arr2) # 3 5 10 15 20 30 

- Kth Smallest element

# TC: O(nlogn)
# SC: O(1)
def kth(arr, k):
    arr.sort()
    return arr[k - 1]

- Minimum difference in an array

# TC: O(nlogn)
# SC: O(1)
import math 

def min_diff(arr):
    arr.sort()
    result = math.inf
    i = 1
    while i < len(arr):
        diff = arr[i] - arr[i-1]
        result = min(result, diff)
        i += 1
    return result

- Chocolate distribution problem

# TC: O(nlogn)
# SC: O(1)
import math 

def min_k_diff(arr, k):
    arr.sort()
    result = math.inf
    i = 0
    while i + k - 1 < len(arr):
        diff = arr[i + k - 1] - arr[i]
        result = min(result, diff)
        i += 1
    return result


print(min_k_diff([7, 3, 2, 4, 9, 12, 56], 3)) # 2
print(min_k_diff([3, 4, 1, 9, 56, 7, 9, 12], 5)) # 6

- Sort an array with two types of elements
- Sort an array with three types of elements
- Merge overlapping intervals

# TC: O(n log n)
# SC: O(n)

def merge_interval(arr):
    def merge_item(item1, item2):
        x1, y1 = item1
        x2, y2 = item2
        if y1 < x2:
            return [item1, item2]
        return [(min(x1, x2), max(y1, y2))]

    arr.sort(key=lambda x: x[0])
    n = len(arr)
    result = []
    for x in range(0, n):
        if x == 0:
            result.append(arr[x])
            continue
        prev = result.pop()
        items = merge_item(prev, arr[x])
        for item in items:
            result.append(item)
    return result


print(merge_interval([(1, 3), (2, 4), (5, 7), (6, 8)])) 
print(merge_interval([(7, 9), (6, 10), (4, 5), (1, 3), (2, 4)]))

- Meeting the maximum guests

# TC: O(n log(n))
# SC: O(1)

def meeting_guest(arr, dep):
    arr.sort()
    dep.sort()
    n = len(arr)
    i = 0
    j = 0

    result = 0
    current = 0
    while i < n and j < n:
        if arr[i] < dep[j]:
            i += 1
            current += 1
        elif dep[j] < arr[i]:
            j += 1
            current -= 1
        elif dep[j] == arr[i]:
            j += 1
            current -= 1
        result = max(result, current)
    return result


print(meeting_guest([900, 940], [1000, 1030])) 
print(meeting_guest([800, 700, 600, 500], [840, 820, 830, 530]))
print(meeting_guest([900, 940, 950, 1100, 1500, 1800], [910, 1200, 1120, 1130, 1900, 2000]))