algorithm - 使用就地合并进行合并排序

Question

A[] -> 1 3 5 7 2 4 6 8//

lb=0,mid-1=3,mid+1=4,ub=7;

a=3,b=7,ab=7;

第一次迭代

a=3,b=6,ab=6;

---

第二次迭代

swap(A[ab],A[a])//整数 t;我将用于临时存储

1 3 5 6 2 4 7 8

b=5,ab=5; 排序(A，lb，mid-1)；//使用冒泡排序

---

第三次迭代

交换(A[ab],A[a])

1 3 5 4 2 6 7 8

b=5,ab=4

sort(A,lb,mid-1)//使用冒泡排序

---

这是使用就地合并进行合并排序的正确方法吗？这是我第一次尝试就地合并。如果方法不正确，有人可以建议我。

Answer 1

不确定您是否有 Mergesort 算法。

在第一阶段使用 Mergesort，您需要将数组拆分为子数组。

A = [1, 3, 5, 7, 2, 4, 6, 8]

A1 = [1, 3, 5, 7], A2 = [2, 4, 6, 8]

A11 = [1,3], A12 = [5,7], A21 = [2,4], A22 = [6,8]
... // till you have an arrays looks like this:
A1 = [1], A2 = [3], A3 = [5], A4 = [7], A5 = [2], A6 = [4], A7 = [6], A8 = [8]

然后以相反的顺序合并，并只比较两个数组中的第一个元素(将最低元素放入新数组中)。

[1,3], [5,7], [2,4], [6,8]
  [1,3,5,7],   [2,4,6,8]
     [1,2,3,4,5,6,7,8]