It is necessary to implement a downward merge sort using the abstract exchange merge method. Here is the abstract exchange merge function:

template <class Item> void merge(Item a[], int l, int m, int r) { int i, j; static Item aux[maxN]; for (i = m + 1; i > l; i--) aux[i - 1] = a[i - 1]; for (j = m; j < r; j++) aux[r + m - j] = a[j + 1]; for (int k = l; k <= r; k++) if (aux[j] < aux[i]) a[k] = aux[j--]; else a[k] = aux[i++]; }

How to make this sorting descending, that is, recursive?

  • 3
    There is no sorting here yet, and there is only a primitive that is used in it (and not only in it): the merging of two sorted arrays. - AnT

1 answer 1

I changed your function a bit. The average is calculated internally. The principle of the algorithm is such that, first, the source array is split into two others. Each of them will also be broken into two more. This will continue until the length of each subarray is 1.

 template <class Item> void merge(Item a[], int l, int r) { if (abs(r - l) <= 1) return; //конец рекурсивных вызовов int i, j; int m = (l + r) / 2; merge(a, l, m); //вызов для левой части merge(a, m+1, r); //вызов для правой части static Item aux[1000]; for (i = m + 1; i > l; i--) aux[i - 1] = a[i - 1]; for (j = m; j < r; j++) aux[r + m - j] = a[j + 1]; for (int k = l; k <= r; k++) { if (aux[j] < aux[i]) a[k] = aux[j--]; else a[k] = aux[i++]; } }

Note: when calling a function, it is necessary to specify the length of the array - 1. That is:

 int main() { int a[N]; merge(a, 0, N-1); }
  • I understand, the question is old, but could you comment on what happens in these cycles, as I understand it, this is where the array is split in two and alternately written into an additional aux array. I was not mistaken anywhere? Tell me where the array is again connected to one? - EDWIN
  • @EDWIN, you wrote these cycles yourself, I just implemented sorting. But in general, the principle is this: it is necessary to divide the array in half, and then merge them according to certain principles. But we cannot merge into the same (source) array, so an additional array is required into which the merge will take place. After the merge is complete, you need to write that merged array into the source array. In this code, where aux [i] = a [j] is the filling of the array into which the two halves merge. A a [i] = aux [j] is a rewrite of the original array - 9Pasha