[자료구조 및 알고리즘] (2) 삽입 정렬과 합병 정렬 (Insertion sort and merge sort)

이번 글의 내용 Sorting이란? Insertion sort Insertion sort ver.1 Insertion sort ver.2 Efficiency of insertion sort "Lower bound" for comparison sort Merge sort Efficiency of merge sort 1.

Sorting이란 지난 시간에 배운 알고리즘의 정의를 통해서 Sorting을 정의해 보자. Input: an array of n elements, whose order is not known.

Output: an array of n elements, sorted in ascending order. Assumptions: n은 2^k 꼴을 하고 있다.

즉, 1, 2, 4, 8, 16 ... 중 하나이다. the elements are distinct: element가 숫자라고 가정할 때, 같은 숫자는 없다. -> 사실 같은 숫자가 있더라도 implementation이 그...