// Array A[] has the items to sort; array B[] is a work array.
function topDownMergeSort(arr1, arr2, n)
{
copyArray(arr1, 0, n, arr2); // duplicate array A[] into B[]
copDownSplitMerge(arr2, 0, n, arr1); // sort data from B[] into A[]
}
// Sort the given run of array A[] using array B[] as a source.
// iBegin is inclusive; iEnd is exclusive (A[iEnd] is not in the set).
function topDownSplitMerge(arr2, iBegin, iEnd, arr1)
{
if(iEnd - iBegin < 2) // if run size == 1
return; // consider it sorted
// split the run longer than 1 item into halves
let iMiddle = (iEnd + iBegin) / 2; // iMiddle = mid point
// recursively sort both runs from array A[] into B[]
topDownSplitMerge(arr1, iBegin, iMiddle, arr2); // sort the left run
topDownSplitMerge(arr1, iMiddle, iEnd, arr2); // sort the right run
// merge the resulting runs from array B[] into A[]
topDownMerge(arr2, iBegin, iMiddle, iEnd, arr1);
}
// Left source half is A[ iBegin:iMiddle-1].
// Right source half is A[iMiddle:iEnd-1 ].
// Result is B[ iBegin:iEnd-1 ].
function topDownMerge(arr1, iBegin, iMiddle, iEnd, arr2)
{
let i = iBegin;
let j = iMiddle;
// While there are elements in the left or right runs...
for (let k = iBegin; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iMiddle && (j >= iEnd || arr1[i] <= arr1[j])) {
arr2[k] = arr1[i];
i = i + 1;
} else {
arr2[k] = arr1[j];
j = j + 1;
}
}
}
function CopyArray(arr1[], iBegin, iEnd, arr2[])
{
for(let k = iBegin; k < iEnd; k++)
arr2[k] = arr1[k];
}
/// merge sort range : [low ~ high]
function mergeSort(arr1, low, high, arr2){
// 1. base condition
if(low >= high) return;
// 2. divide
let mid = (low + high) / 2;
// 3. conquer
mergeSort(arr1, low, mid, arr2);
mergeSort(arr1, mid+1, high, arr2);
// 4. combine
let i = low;
let j = mid+1;
let k=low;
for(;k<=high;++k){
if(j > high ) {
arr2[k] = arr1[i++];
} else if(i > mid) {
arr2[k] = arr1[j++];
} else if {
(arr1[i] <= arr1[j]) arr2[k] = arr1[i++];
} else {
arr2[k] = arr1[j++];
}
}
// 5. copy
for(;i<=high;++i) {
arr1[i] = arr2[i];
}
}
function bottomUpMergeSort(arr1, arr2, n)
{
// Each 1-element run in A is already "sorted".
// Make successively longer sorted runs of length 2, 4, 8, 16... until whole array is sorted.
for (let width = 1; width < n; width = 2 * width)
{
// Array A is full of runs of length width.
for (let i = 0; i < n; i = i + 2 * width)
{
// Merge two runs: A[i:i+width-1] and A[i+width:i+2*width-1] to B[]
// or copy A[i:n-1] to B[] ( if(i+width >= n) )
bottomUpMerge(arr1, i, Math.min(i+width, n), Math.min(i+2*width, n), arr2);
}
// Now work array B is full of runs of length 2*width.
// Copy array B to array A for next iteration.
// A more efficient implementation would swap the roles of A and B.
copyArray(B, A, n);
// Now array A is full of runs of length 2*width.
}
}
// Left run is A[iLeft :iRight-1].
// Right run is A[iRight:iEnd-1 ].
function bottomUpMerge(arr1, iLeft, iRight, iEnd, arr2)
{
let i = iLeft;
let j = iRight;
// While there are elements in the left or right runs...
for (let k = iLeft; k < iEnd; k++) {
// If left run head exists and is <= existing right run head.
if (i < iRight && (j >= iEnd || A[i] <= A[j])) {
arr2[k] = arr1[i];
i = i + 1;
} else {
arr2[k] = arr1[j];
j = j + 1;
}
}
}
function copyArray(arr2, arr1, n)
{
for(let i = 0; i < n; i++)
arr1[i] = arr2[i];
}
- 안정 정렬(stable sort)
- 중복된 값을 입력 순서와 동일하게 정렬한다. 예를 들어 다음 그림과 같이 지역별 발송 시각을 시간 순으로 정렬한 택배 발송 로그가 있다고 가정해보자. 안정 정렬의 경우에는 기존의 시간 순으로 정렬했던 순서는 지역명으로 재정렬하더라도 기존 순서가 그대로 유지된 상태에서 정렬이 이뤄진다. 그러나 불안정 정렬의 경우에는 시간순으로 정렬한 값을 지역명으로 재정렬하면 기존의 정렬 순서는 무시된 채 모두 뒤죽박죽 뒤섞이고 만다