Node.js에서 기본 정렬 / 합병정렬 / 퀵정렬 속도 비교

"The misty downtown Seoul landscape depicted by Simon Stålenhag, 1990s, morning" from DALL-E 2

실험환경

• 값의 범위 : 0~1억
• 데이터 개수 : 천만개 ~ 3천만개
• 반복횟수 : 3회
• Note : 합병정렬은 기본 배열의 두배 크기로 메모리 공간을 사용합니다.

실험결과

	1000만	1500만	2000만	2500만	3000만
기본정렬	4.16초	6.845초	9.142초	11.421초	14.021초
합병정렬	2.632초	3.881초	5.225초	6.589초	8.358초
퀵정렬	2.129초	3.172초	4.261초	5.487초	6.557초

/** INFO: 파라미터 만큼 배열을 생성하고 랜덤값 입력 */
function generateRandomArray(numData){
    let arr = new Array(numData).fill(0);
    for(let i=0;i<numData;i++){
        arr[i] = Math.round(Math.random() * 100000000);
    }
    return arr;
}

function quickSort(arr){
    let stack = [];
    let low = 0, high = arr.length - 1;
    let pivot, tmp;
    let i, j;
    stack.push(high);
    stack.push(low);
    while(stack.length !== 0){
        low = stack.pop();
        high = stack.pop();
        let curLength = high - low + 1;
        if(low >= high){
            //INFO: 한개밖에 없으면 continue
            continue;
        }

        if(curLength > 2) {
            //INFO: 2개 이상인 경우
            let tmpMid = Math.round((low+high) / 2);
            //INFO: low, mid, high 중 중간값을 정해야 함
            let tmpArr = [low, tmpMid, high];
            tmpArr.sort((a,b) => {return arr[a]-arr[b]});
            pivot = tmpArr[1];

            {//SWAP
                tmp = arr[high];
                arr[high] = arr[pivot];
                arr[pivot] = tmp;
            }

            pivot = high;
        } else {
            //INFO: 2개 밖에 없는 경우
            if(arr[low] > arr[high]){
                //SWAP
                tmp = arr[low];
                arr[low] = arr[high];
                arr[high] = tmp;
            }
            continue;
        }

        //INFO: 피봇
        pivot = arr[high];
        i = low - 1;
        j = high;
        while(true){
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            if(i >= j) break;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        tmp = arr[i];
        arr[i] = arr[high];
        arr[high] = tmp;
        stack.push(high);
        stack.push(i+1);
        stack.push(i-1);
        stack.push(low);
    }
}

function mergeSort(arr, low, high){
    if(low === high){
        //INFO: 비교 데이터가 하나밖에 없음
        return;
    } else if(high - low === 1){
        //INFO: 두개밖에 없음
        if(arr[low] > arr[high]){
            //INFO: 좌측이 더 큰 값이면 교환
            let tmp = arr[low];
            arr[low] = arr[high];
            arr[high] = tmp;
        }
        return;
    }

    //INFO: 비교 데이터가 세 개 이상이면 쪼갠다
    let mid = Math.round((low + high) / 2);
    
    mergeSort(arr, low, mid);
    mergeSort(arr, mid + 1, high);

    let a = low, b = mid + 1;
    let pos = low;
    while(true){
        if(arr[a] < arr[b]){
            brr[pos++] = arr[a++];
        } else if(arr[a] > arr[b]){
            brr[pos++] = arr[b++];
        } else {
            //INFO: 같음
            brr[pos++] = arr[a++];
            brr[pos++] = arr[b++];
        }
        if(a > mid) break;
        else if(b > high) break;
    }
    while(a <= mid) brr[pos++] = arr[a++];
    while(b <= high) brr[pos++] = arr[b++];
    
    for(let i=low;i<=high;i++) arr[i] = brr[i];
} 

function main(){
    let numData = 10000000;
    console.log('Start Sort; data size : ' + numData);
    for(let i=0;i<5;i++){
        let arr = generateRandomArray(numData);
        console.time('quick_sort');
        quickSort(arr);
        console.timeEnd('quick_sort');

        arr = generateRandomArray(numData);
        console.time('merge_sort');
        mergeSort(arr, 0, numData - 1); 
        console.timeEnd('merge_sort'); 

        arr = generateRandomArray(numData);
        console.time('basic_sort');
        arr.sort((a,b) => {return a-b});
        console.timeEnd('basic_sort');
    }
}
main();