[알고리즘] 자바를 이용해 비교, 분석한 삽입 정렬과 병합 정렬의 시간 복잡도(수행 시간)

1. 오름차순으로 이미 정렬 되어있는 상태의 배열을 정렬

삽입 정렬과 병합 정렬의 시간 복잡도를 비교할 때, 특정한 배열 상태, 특히 오름차순으로 이미 정렬된 배열에 대한 성능을 분석하는 것이 중요하다. 오름차순으로 정렬된 배열을 삽입 정렬로 처리할 경우 가장 최적의 상황이 발생한다. 삽입 정렬의 기본 작동 원리는 배열의 각 요소를 하나씩 차례대로 확인하며, 현재 요소보다 작은 요소들 앞에 위치할 수 있도록 삽입하는 방식이다. 이미 정렬된 배열이라면, 각 요소는 자신의 위치에서 그대로 유지되며, 이동할 필요가 없다. 따라서, 각 요소를 한 번씩만 확인하기 때문에 시간 복잡도는 O(n)으로 이루어진다. 여기서 n은 정렬할 데이터의 개수다. 대조적으로 병합 정렬은 항상 O(n log n)의 시간 복잡도를 가지며, 이 경우에도 예외 없이 같은 복잡도를 유지한다. 병합 정렬은 배열을 반으로 나누고, 각각을 정렬한 뒤 다시 합치는 방식으로 작동한다. 정렬이 필요 없이 배열이 이미 정렬되어 있더라도 각 단계에서 배열을 나누고 병합하는 작업을 지속적으로 함으로써 시간을 소모한다. 이러한 병합 과정에서는 두 개의 정렬된 리스트를 하나로 합치는 작업…