O(n log n) — Linearithmic Time

// ทำ O(log n) ซ้ำสำหรับทุก element → O(n log n)
function totalHalvings(arr) {
  let total = 0;
  for (const num of arr) {          // ← n รอบ
    let n = num;
    while (n > 1) {                  // ← log(n) รอบ
      n = Math.floor(n / 2);
      total++;
    }
  }
  return total;
}

console.log(totalHalvings([8, 16, 32])); // 3+4+5 = 12

// Merge sort: split → sort → merge
//
// [38, 27, 43, 3, 9, 82, 10]
// → [38, 27, 43, 3]  [9, 82, 10]        ← แบ่งครึ่ง
// → [38, 27] [43, 3] [9, 82] [10]       ← แบ่งครึ่งซ้ำ
// → [27, 38] [3, 43] [9, 82] [10]       ← merge แต่ละคู่
// → [3, 27, 38, 43] [9, 10, 82]         ← merge ใหญ่ขึ้น
// → [3, 9, 10, 27, 38, 43, 82]          ← merge สุดท้าย
//
// 3 ระดับ (log₂7 ≈ 3) × 7 ตัว = ~21 ขั้นตอน
// เทียบกับ bubble sort: 7² = 49 ขั้นตอน

const sorted = [1, 3, 5, 7, 9, 11, 13];
const targets = [3, 7, 13, 2];

// สำหรับทุก target → binary search ใน sorted array
// n targets × O(log n) search = O(n log n)
const results = targets.map((t) => binaryContains(sorted, t));

console.log(results); // [true, true, true, false]

function binaryContains(arr, target) {
  let left = 0, right = arr.length - 1;
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return true;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }
  return false;
}

function merge(a, b) {
  const result = [];
  let i = 0, j = 0;

  // เทียบตัวหน้าสุดของแต่ละ array
  while (i < a.length && j < b.length) {
    if (a[i] <= b[j]) result.push(a[i++]);
    else result.push(b[j++]);
  }
  // เติมที่เหลือ
  while (i < a.length) result.push(a[i++]);
  while (j < b.length) result.push(b[j++]);

  return result;
}

console.log(merge([1, 4, 7], [2, 3, 6, 8]));
// [1, 2, 3, 4, 6, 7, 8]

// ❌ n + log n = O(n) — ไม่ใช่ O(n log n)
for (let i = 0; i < arr.length; i++) { }  // O(n)
let n = arr.length;
while (n > 1) { n = Math.floor(n / 2); }  // O(log n)
// รวม = O(n) + O(log n) = O(n)

// ❌ ซ้อน 2 ชั้นทั้งคู่วิ่ง n = O(n²) ไม่ใช่ O(n log n)
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) { }
}

// ❌ loop เดียววิ่ง n = O(n) ไม่ใช่ O(n log n)
for (const x of arr) { console.log(x); }