정렬

def selection_sort(arr):
    for i in range(0, len(arr)):
        min_idx = i

        for j in range(i, len(arr)):
            # 1. 주어진 배열 중에 최소값을 찾는다.
            if arr[j] < arr[min_idx]:
                min_idx = j

        # 2. 그 값을 맨 앞에 위치한 값과 교체한다.
        # 3. 맨 처음 위치를 뺀 배열을 같은 방법으로 교체
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

    return arr

def insertion_sort(arr):
	
	for cur_idx in range(1, len(arr)):
		cur = arr[cur_idx]
		prev_idx = cur_idx - 1
		
		while prev_idx >= 0 and arr[prev_idx] > cur:
			arr[prev_idx + 1] = arr[prev_idx]
			prev_idx -= 1
		
		arr[prev_idx + 1] = cur
		
	return arr

def quick_sort(arr, start, end):
    # 원소가 1개일 경우 바로 종료
    if start >= end:
        return arr

    pivot = start
    left = start + 1
    right = end

    # 왼쪽에는 피벗보다 작은 수, 오른쪽은 피벗보다 큰 수
    while left <= right:
        while left <= end and arr[left] <= arr[pivot]:
            left += 1

        while right > start and arr[right] >= arr[pivot]:
            right -= 1

        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot]
        else:
            arr[left], arr[right] = arr[right], arr[left]

    quick_sort(arr, left, right - 1)
    quick_sort(arr, right + 1, end)

    return arr

def merge(left_half, right_half):
    result = []
    i = j = 0

    while i < len(left_half) and j < len(right_half):
        if left_half[i] < right_half[j]:
            result.append(left_half[i])
            i += 1
        else:
            result.append(right_half[j])
            j += 1

    result.extend(left_half[i:])
    result.extend(right_half[j:])

    return result


def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2

    # left, right 반으로 나눈다.
    left_half = arr[:mid]
    right_half = arr[mid:]

    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 왼쪽과 오른쪽을 합친다.
    return merge(left_half, right_half)

count_list = [0] * (max(arr) + 1)

# 이후 모든 원소를 돌면서 count_list에 추가

[0,0,1,2,2,3,3,3] # count list에 있는 값들을 차례대로 출력