?? ????? ?? ??, ?? ??, ?? ?? ? ??? ?? ????? ?? ?????. ??? ??? ?? ????? ????? ?? ??? ??? ??? ???? ????? ??? ?? ?????. ?, ??? ??? ?? ??? ????? ? ???? ????? ????? ?? ??? ?????. ?? ?????? ?? ??? ?? ??? ?? JavaScript? ???? ??? ???????. ??????

??

1. ?? ?? ?????? ??????
2. ?? ?? ????? ?? ??
   • ?????
   • ?? ???
3. JavaScript? ??
4. ??

?? ?? ?????? ??????

?? ?? ????? ?? ?? ??? ??? ??? ?? ???????. ??? ??? ???? ??? ?? ? ???? ?? ?? ? ?? ??? ?? ??? ????? ?? ?? ??? ?? ???? ?? ??? ????.

1. ??: ?? ?? ??? ??? ? ???? ????
2. ??: ??, ? ??? ????? ??
3. ??: ????? ??? ??? ?? ?????

? ?? ??? ??? ?????? ??? ? ?? ?? ? ?? ??? ?? ??? O(n2) ?????? ????? ??? ?????.

?? ?? ????? ?? ??

??? ?? ???? ?? ?? ?? ??? ???? ?? ??? ???? ?? ??????. ??? ?? ??? ????? ??? ????.

?? ??? ????? ??? ??? ?? ??? ???? [38, 27, 43, 3, 9, 82, 10] ??? ???? ???? ?? ?? ????? ???? ??? ???????.

1??: ???

?? ??? ? ?? ??? ??? ?? ??? ?? ?? ?? ?? ??? ??? ??? ?? ??? ? ?? ??? ?? ???, ?? ??? ?? ??? ??? ????.

2??: ?? ??(??)

? ?? ??? ?? ?? ??? ???? ???? ????.

?? ???

?? ??? ?? ??(??, ??, ??)?? O(n log n) ?? ???? ????? ? ? ??? ??? ?? O(n2) ?????? ? ??????.

??? ??? ????.

• ???: ??? log n ? ????(? ???? ??? ???? ????)
• ??: ? ?? ???? n?? ??? ?????
• ??: n? ?? × log n ?? = O(n log n)

??:

• ?? ??: O(n2)
• ?? ??: O(n2)
• ?? ??: O(n log n)

1,000? ?? ??? ??:

• O(n2) ≒ 1,000,000? ??
• O(n log n) ≒ 10,000 ??

?? ???

?? ???? ?? ?? ?? ??? ???? ?? O(n)?? ?? ??? ?????. ?? ?? ?? ?? ?? ??? ??? O(1) ???? ??? ?? ????? ?? ????? ??? ??? ???? ?? ?? ????.

JavaScript? ??

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

?? ?? ??:

1. ?? ??:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

• ??? ??? ??? ? ??? ????
• ? ?? ?? ??? ?? ???? ??????
• ??? ???? ? ??? ??? ?????? ???? ??? ?????

1. ?? ?? ??:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

• ? ??? ??? ?????
• ? ?? ??? ???? ??? ?????
• ??? ??? ???? ???? ??? ?????
• ?? ??? ? ? ?? ?? ? ?? ?? ???? ???

1. ?? ??:

   while (leftIndex < left.length) {
     result.push(left[leftIndex]);
     leftIndex++;
   }

• ??? ?? ??
• ? ??? ?? ???? ? ? ???? ?????
• ???? ?? ?? ???

?? ?? ?? ??

function mergeSort(arr) {
  // Base case
  if (arr.length <= 1) {
    return arr;
  }

  // Divide
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  // Conquer and Combine
  return merge(mergeSort(left), mergeSort(right));
}

?? ?? ??:

1. ?? ??:

   if (arr.length <= 1) {
     return arr;
   }

• ??? 0 ?? 1? ??? ?????
• ??? ?? ?? ???? ????
• ?? ?? ?? ??? ???

1. ?? ??:

   const middle = Math.floor(arr.length / 2);
   const left = arr.slice(0, middle);
   const right = arr.slice(middle);

• ??? ? ???? ??
• Slice()? ??? ???? ?? ? ??? ?????
• ?? ? ?? ??? ??? ?? ????

1. ?? ?? ? ??:

   return merge(mergeSort(left), mergeSort(right));

• ? ??? ????? ??
• ?? ??? ???? ??? ??? ??
• ?? ?? ??? ???? ?? ???? ?? ????

?? ??

[38, 27, 43, 3]? ??? ????? ???????.

1. ? ?? ??:

// The Merge Helper Function
function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] <= right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  // Add remaining elements
  while (leftIndex < left.length) {
    result.push(left[leftIndex]);
    leftIndex++;
  }

  while (rightIndex < right.length) {
    result.push(right[rightIndex]);
    rightIndex++;
  }

  return result;
}

1. ? ?? ??:

   const result = [];
   let leftIndex = 0;
   let rightIndex = 0;

1. ?? ??:

   while (leftIndex < left.length && rightIndex < right.length) {
     if (left[leftIndex] <= right[rightIndex]) {
       result.push(left[leftIndex]);
       leftIndex++;
     } else {
       result.push(right[rightIndex]);
       rightIndex++;
     }
   }

??

?? ??? ??? ??? ???? ???? ?? ??? ???? ?? ???? ?? ???????. ??? ?? ????? ?? ?? ??? ????? O(n log n) ?? ????? ?? ??? ??? ?? ?? ??????? ?????.

?? ??:

• ?? ?? ??? ?????
• ?? ??? O(n log n) ?? ???
• O(n) ?? ?? ??
• ???? ?? ????
• ??? ?????? ??

---

---

?? ??? ?? ??? ?????

? ???? ?? ??? ??? ??? ?? ?? ? ?? ?? ???? ??
????? ??(?, ??, ??? ?? ????/???), ???? ?? ??
??? ????, ?? ???? ?? ??? ?? ????? ?? ??????.

• ???
• ????
• ??(???)

??? ?? ??? ??? ????. ??? ?? ??? ????

? ??? ?? ?? ???? ??: ?? ???? ???? ?? ??? ???? ?? ?????. ??? ??? PHP ??? ????? ?? ?? ??? ?????!