如何用MergeSort对JS对象数组按categoryName属性字母排序

给定如下JS对象数组filteritem，需要基于categoryName属性按字母顺序排序，要求必须实现归并排序（MergeSort）算法，不可使用filter、includes等方法，预期排序结果顺序为：admission、Binodkhatricv、officialdocument、syallabus。

原数组数据：

const filteritem = [
  {
    "categoryName": "admission",
    "rows": [
      {
        "uploaddate": "8/8/2022",
        "title": "binoddocs",
        "view": "https://firebasestorage.googleapis.com/v0/b/auth",
        "fullname": "bruno",
        "id": "B8QsXYVFH8fHt3PrBYUp"
      }
    ]
  },
  {
    "categoryName": "officialdocument",
    "rows": [
      {
        "file": null,
        "uploadedby": "bruno",
        "uploaddate": "6/27/2022",
        "title": "sudhikchaadmission",
        "view": "https://firebasestorage.googleapis.com/v0/b/auth",
        "id": "Z27GLizWnYTJvLQyYRQt"
      },
      {
        "view": "https://firebasestorage.googleapis.com/v0/b/auth",
        "uploadedby":"bruno",
        "uploaddate":"6/27/2022",
        "title":"ankitadmission",
        "file":null,
        "id":"rmcbUrg9TpFhQh5RLqva"
      }
    ]
  },
  {
    "categoryName":"syallabus",
    "rows": [
      {
        "fullname":"bruno",
        "view":"https://firebasestorage.googleapis.com/v0/b/auth",
        "title":"sudhir",
        "uploaddate":"8/15/2022",
        "id":"hi7QEOlBzzVLZ1QHYqlk"
      }
    ]
  },
  {
    "categoryName":"Binodkhatricv",
    "rows": [
      {
        "title":"binodtry",
        "fullname":"bruno",
        "uploaddate":"8/15/2022",
        "view":"https://firebasestorage.googleapis.com/v0/b/auth",
        "id":"o4EtP1xkbWMk1icp4uNH"
      }
    ]
  }
];

预期排序后数组：

[
  {categoryName:"admission", ...},
  {categoryName:"Binodkhatricv", ...},
  {categoryName:"officialdocument", ...},
  {categoryName:"syallabus", ...}
]

归并排序的核心是分治法：先把数组递归拆分成最小单元，再两两合并排序，最终得到有序数组。这里基于categoryName的字母序（区分大小写，符合JS字符串默认比较规则）实现。

实现代码 #

// 合并两个已排序的子数组
function merge(left, right) {
  let result = [];
  let leftIdx = 0;
  let rightIdx = 0;

  // 按categoryName比较，依次取较小的元素加入结果
  while (leftIdx < left.length && rightIdx < right.length) {
    if (left[leftIdx].categoryName < right[rightIdx].categoryName) {
      result.push(left[leftIdx]);
      leftIdx++;
    } else {
      result.push(right[rightIdx]);
      rightIdx++;
    }
  }

  // 追加剩余未合并的元素
  while (leftIdx < left.length) {
    result.push(left[leftIdx]);
    leftIdx++;
  }
  while (rightIdx < right.length) {
    result.push(right[rightIdx]);
    rightIdx++;
  }

  return result;
}

// 归并排序主函数：递归拆分并排序
function mergeSort(arr) {
  // 递归终止条件：数组长度<=1时直接返回
  if (arr.length <= 1) {
    return arr;
  }

  // 拆分数组为左右两部分
  const mid = Math.floor(arr.length / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  // 递归排序左右子数组后合并
  return merge(mergeSort(left), mergeSort(right));
}

// 执行排序
const sortedFilterItems = mergeSort(filteritem);
console.log(sortedFilterItems);

结果说明 #

执行代码后，sortedFilterItems会严格符合预期顺序：

1. admission（小写开头，ASCII码小于大写B）
2. Binodkhatricv（大写B开头）
3. officialdocument（小写o，ASCII码大于B）
4. syallabus（小写s，ASCII码最大）

内容的提问来源于stack exchange，提问作者alex