•
하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
•
분할 정복 방법을 통해 구현
Process
1.
list를 절반으로 잘라 비슷한 크기의 두 부분 list로 나눈다
2.
각 부분 list를 재귀적으로 합병 정렬을 이용해 정렬한다.
3.
두 부분 list를 다시 하나의 정렬된 리스트로 합병한다.
def merge_sort(data):
if len(data) > 1:
mid = len(data) // 2
left, right = data[:mid], data[mid:]
merge_sort(left)
merge_sort(right)
li, ri, i = 0, 0, 0
while li < len(left) and ri < len(right):
if left[li] < right[ri]:
x[i] = left[li]
li += 1
else:
x[i] = right[ri]
ri += 1
i += 1
data[i:] = left[li:] if li != len(left) else right[ri:]
Python
복사
JavaScript
const mergeSort = function (arr) {
if (arr.length < 2) {
return arr;
}
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
return merge(mergeSort(left), mergeSort(right));
function merge (left, right) {
const resultArray = [];
let leftIndex = 0;
let rightIndex = 0;
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
resultArray.push(left[leftIndex]);
leftIndex++;
} else {
resultArray.push(right[rightIndex]);
rightIndex++;
}
}
return resultArray.concat(left.slice(leftIndex), right.slice(rightIndex));
}
};
JavaScript
복사
•
시간 복잡도 : O()
•
공간 복잡도
장점
•
안정 정렬
•
합병정렬은 순차적인 비교로 정렬을 진행하므로, LinkedList의 정렬이 필요할 때 사용하면 효율적
단점
•