병합 정렬(merge Sort) - 자바스크립트(JS), C#(씨샵)

자바스크립트 코드(Javascript JS)

function mergeSort(arr){

  if(arr.length<2){

    return arr;

  }

  const mid = Math.floor(arr.length/2);

  const leftArr = arr.slice(0,mid);

  const rightArr = arr.slice(mid);

  return merge(mergeSort(leftArr), mergeSort(rightArr))

}

function merge(leftArr, rightArr){

  const sortedArr = [];

  while(leftArr.lenght && rightArr.length){

    if(leftArr[0] <= rightArr[0]){

      sortedArr.push(leftArr.shift())

    }else{

      sortedArr.push(rightArr.shift())

    }

  }

  return [...sortedArr, ...leftArr, ...rightArr]

// 새로운 배열에 sortedArr를 복사하고, leftArr, rightArr 순으로 추가함

}

const arr = [8, 20, -2, 4, -6];

console.log(mergeSort(arr)); //-6 -2 4 8 20

// O(nlogn)

 

C# 코드(씨샵 CSharp)

namespace CodeTest

{

    internal class Program

    {

       

        static void Divide(int[] arr, int leftIdx, int rightIdx)

        {

            if (leftIdx == rightIdx) return;

            // 1.나누기

            int midIdx = (leftIdx + rightIdx) / 2;

            Divide(arr, leftIdx, midIdx);

            Divide(arr, midIdx+1, rightIdx);

            SortAndMerge(arr, leftIdx, midIdx,rightIdx);

        }

        static void SortAndMerge(int[] arr, int leftIdx, int midIdx, int rightIdx)

        {

            int leftArrLength = midIdx - leftIdx + 1;

            int rightArrLength = rightIdx - midIdx;

            int[] leftArr = new int[leftArrLength];

            int[] rightArr = new int[rightArrLength];

            //1.나누기

            for (int m = 0; m < leftArrLength; m++)

            {

                leftArr[m] = arr[leftIdx+m];

            }

            for (int m = 0; m < rightArrLength; m++)

            {

                rightArr[m] = arr[midIdx + 1 + m];

            }

            //2.정렬과 합치기 동시 진행

            int i = 0, j = 0;

            int k = leftIdx;

            while ( i < leftArrLength  && j < rightArrLength)

            {

                if (leftArr[i] > rightArr[j])

                {

                    arr[k++] = rightArr[j++];

                }

                else

                {

                    arr[k++] = leftArr[i++];

                }

            }

            while (i < leftArrLength )

            {

                arr[k++] = leftArr[i++];

            }

            while (j < rightArrLength)

            {

                arr[k++] = rightArr[j++];

            }

        }

        static void Main(string[] args)

        {

            int[] arr = { 3, 2, 1, 5, 4, 8, 7, 6, 10, 9, 11 };

            Divide(arr,0,arr.Length - 1);

            foreach (var el in arr)

            {

                Console.WriteLine(el);  //1 2 3 4 5 6 7 8 9 10 11

            }

        }

    }

}