동작 방식
- 반씩 쪼개서 합쳐 나가는 형태로 정렬을 한다.
- 모두 쪼개서 한개의 요소로 구성된 그룹으로 만든다.
- 그런다음 두개를 비교 할때 작은것을 앞으로 넣어 두개씩 그룹을 만든다.
- 그런다음 두그룹에서 맨앞에 있는 값중에 작은 값을 먼저 넣으면서 4개짜리 그룹을 만든다.
- 해당 작업을 반복을 하면 데이터의 갯수(N) 전체 반복작업 횟수 log8 = 3으로 NlogN을 보장한다.
장점
- O(NlogN)을 보장한다.
단점
- 기존 데이터를 추가로 담을 메모리 공간이 필요해서 메모리 활용에 비효율 적이다.
시간 복잡도
O(NlogN)
- 8개의 데이터가 있다 가정하면 데이터의 갯수(N) 전체 반복작업 횟수 log 2에 8 = 3으로 NlogN을 보장한다.
python 구현
'''
@ Author : bsh0817
@ Created : 2020. 01. 26
@ Update : 2020. 01. 26
@ Description : Merge sort (병합 정렬)
- 전역 변수로 사용 하면 메모리 사용 측면에서 효율 적이지만 그렇게 하지 않았다.
'''
def fn_merge_sort(list_input):
'''
@Description: Merge sort (병합 정렬)
@Arguments Example
list_input = [10, 5, 1, 8, 4, 3, 2, 9, 6, 7]
'''
int_len_list_input = len(list_input)
list_init = []
int_merge_group_index_count = 1
while int_len_list_input > int_merge_group_index_count:
int_end_index = 0
while int_end_index < int_len_list_input:
int_index_b = int_end_index + int_merge_group_index_count*1
int_index_c = int_index_b + int_merge_group_index_count*1
list_init += fn_merge_list(list_input[int_end_index:int_index_b], list_input[int_index_b:int_index_c])
int_end_index = int_index_c
list_input = list_init
list_init = []
int_merge_group_index_count *= 2
return list_input
def fn_merge_list(list_a, list_b):
'''
@Description: Merge list
@Arguments Example
list_a = [1, 3]
list_b = [2, 4]
'''
int_len_a = len(list_a)
int_len_b = len(list_b)
int_index_a = 0
int_index_b = 0
responce = []
while int_index_a < int_len_a or int_index_b < int_len_b != 0:
if int_index_b == int_len_b or (int_index_a < int_len_a and list_a[int_index_a] <= list_b[int_index_b]):
responce += [list_a[int_index_a]]
int_index_a += 1
else:
responce += [list_b[int_index_b]]
int_index_b += 1
print("fn_merge_list : " + str(responce))
return responce
if __name__ == "__main__":
list_fn_merge_sort_param = [10, 1, 5, 8, 4, 3, 2, 9, 6, 7]
print(fn_merge_sort(list_fn_merge_sort_param))