Home>

Regarding merge sort, when I output L [i] on the third line from the top in void marge,
If the input is n = 8, A [i] = 8 7 6 5 4 3 2 1, then L [i] is 8 6 7 8 4 2 3 4 5 6 7 8.

When A [i] = 8 7 6 5 4 3 2 1 is merge-sorted,
8 7 6 5 4 3 2 1
7 8 5 6 3 4 1 2
5 6 7 8 1 2 3 4
1 2 3 4 5 6 7 8
I thought, but what does this L [i] represent?

And why is 5678 stored in L [i] instead of 1234 at the end (?)?

It may be a basic question, but thank you.

#include
using namespace std;
#define INFTY 2000000000
#define MAX 500000
int L [250000 + 2], R [250000 + 2];
int t = 0;
void marge (int A [], int left, int mid, int right) {
    int n1 = mid --left;
    int n2 = right --mid;
    for (int i = 0;i>n;
    for (int i = 0;i>A [i];
    margeSort (A, 0, n);
    for (int i = 0;i


					
				
								
				
				
	
  • Answer # 1

    void print (int L [], int n1, int R [], int n2)
    {
        cout<<"L: ["<<L [0];
        for (int i = 1;i<n1;i ++) cout<<'''<<L [i];
        cout<<"] \ t \ tR: ["<<R [0];
        for (int i = 1;i<n2;i ++) cout<<'''<<R [i];
        cout<<"] \ n";
    }
        for (int i = 0;i<n1;i ++) L [i] = A [left + i];// Here!
        for (int i = 0;i<n2;i ++) R [i] = A [mid + i];
        print (L, n1, R, n2);


    In this way, the execution result is as follows.

    8
    8 7 6 5 4 3 2 1
    L: [8] R: [7]
    L: [6] R: [5]
    L: [7 8] R: [5 6]
    L: [4] R: [3]
    L: [2] R: [1]
    L: [3 4] R: [1 2]
    L: [5 6 7 8] R: [1 2 3 4]
    1 2 3 4 5 6 7 8
    twenty four


    In merge sort, the input [8 7 6 5 4 3 2 1]
    Divide into [8 7 6 5] and [4 3 2 1].

    Then divide [8 7 6 5] into [8 7] and [6 5].

    Then divide [8 7] into [8] and [7].
    This is the first L: [8] R: [7].
    It will be merged into [7 8], but the debug display is still ahead.

    Then divide [6 5] into [6] and [5].
    This is the second L: [6] R: [5].
    It will be merged into [6 5].
    And it will be the third L: [78] R: [56].
    It will be merged into [5 6 7 8], but the debug display will be the last.

    Sort by [4 3 2 1] in the same way.

    Finally, merge L: [5 6 7 8] R: [1 2 3 4].