#!/usr/bin/python
# -*- coding: UTF-8 -*-

def sort_merge_start(arr):

  print(arr)
  sort_arr = arr[:]
  sort_merge(sort_arr, 0, len(arr), 0)
  print(sort_arr)
  return sort_arr


def sort_merge(sort_arr, start_index, end_index, depth):
  
  # test 시 호출 횟 수 제한
  # if depth > 2:
  #   return
  depth += 1

  # 최소 크기 사이즈가 되면 재귀 멈춤
  if len(sort_arr[start_index:end_index]) < 2:        
    return

  mid_index = (start_index + end_index) // 2          

  print("depth", depth, 
        "start_index", start_index, 
        "mid_index", mid_index, 
        "end_index", end_index, 
        "arr", sort_arr)

  sort_merge(sort_arr, start_index, mid_index, depth)
  sort_merge(sort_arr, mid_index, end_index, depth)

  merge(sort_arr, start_index, mid_index, end_index)


# 두 array 앞에서 부터 작은 숫자 먼저 꺼내어
# 하나의 array 로 merge
# start_index: 전체 array 기준으로 merge 대상의 start index
# mid_index:   전체 array 기준으로 merge 대상의 두 array 나눈 기준 index
# end_index:   전체 array 기준으로 merge 대상의 end index
def merge(sort_arr, start_index, mid_index, end_index):

  front_arr = sort_arr[start_index:mid_index]
  back_arr = sort_arr[mid_index:end_index]

  front_index = 0
  back_index = 0

  tar_index = start_index

  while front_index < len(front_arr) and back_index < len(back_arr):

    front_val = front_arr[front_index]
    back_val = back_arr[back_index]

    if front_val < back_val:
      front_index += 1
      sort_arr[tar_index] = front_val
    else:
      back_index += 1
      sort_arr[tar_index] = back_val

    tar_index += 1

  # 앞 array 에서 꺼내지지 않은 숫자들은
  # 앞뒤 array 합친 범위내에서
  # 마지막으로 정렬된 index 부터 끝까지 이동
  # 뒤 array가 남았을 경우는 값이 동일하므로 생략
  if (front_index != len(front_arr)) :
    sort_arr[tar_index:end_index] = front_arr[front_index:len(front_arr)]

  # print("sorted", sort_arr)

#!/usr/bin/python
# -*- coding: UTF-8 -*-

# O(nlogn)
# worst O(n^2)
def sort_quick_start(arr):
  sort_quick(arr, 0, len(arr)-1)
  return arr


def sort_quick(arr, start_index, end_index):
  
  if end_index <= start_index:
    return
  
  partition_index = partition(arr, start_index, end_index)

  if start_index < (partition_index-1):
    sort_quick(arr, start_index, partition_index-1)

  if partition_index < end_index:
    sort_quick(arr, partition_index, end_index)

# 마지막 정렬 지점을 partition 위치로 리턴
# start_index < end_index 이어야한다.
def partition(arr, start_index, end_index):

  pivot_index = (start_index + end_index) // 2
  pivot_value = arr[pivot_index]

  while start_index < end_index:

    while start_index < end_index and arr[start_index] < pivot_value:
      start_index += 1

    while start_index < end_index and pivot_value < arr[end_index]:
      end_index -= 1

    arr[start_index], arr[end_index] = arr[end_index], arr[start_index]
    start_index += 1
    end_index -= 1

  return start_index