Home>

### c ++ about merge sort

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

``` c c++ sort merge ```
``` 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); (adsbygoogle = window.adsbygoogle || []).push({}); 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 (adsbygoogle = window.adsbygoogle || []).push({}); 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]. Related articlesabout c ++ bubble sortabout the meaning of c ++ (struct-like) codec ++ - about the return value of the constructorc ++ - questions about passing by value and passing by referencec ++ - about getting the number of elements in a two-dimensional arrayc ++: about stack overflowabout embedding random numbers in c ++ output file names[c ++] about inherited class functions [rust]c ++ - about test case outputc ++ - confirmation about constexprabout measuring the average processing time during continuous execution in c ++about deleting c ++ structure arrayabout the problem that characters are garbled when accessing the list of uint8_t in c ++about the error when linking multiple c ++ files with makefilec ++ - about initialization and assignment of reference objectc ++ - about atcoder environment constructionc ++ - about gnuplot hourly 3d animationc ++ - about the behavior of the program when inserting the first value into the binary search treeabout the associative law of c ++ 20 templates ```
``` Related questions resolution of unknown type name'a', which is a c ++ errori want to know the reason for killing when declaring an array in the main function (c ++)c ++ - reasons to declare an array globallyc ++ - i want to change the screen brightness by briefly pressing the power button on the m5stick cc ++ - i want to port the functionalized fizzbuzz implemented in ruby to c languagec ++ - i get fatal error: bits/error_constantsh: no such file or directory when compiling with arduino idec ++ - how to convert from a floating decimal value to a fixed minority valuec - sometimes heapsort does not sort wellc ++ - mpu6886 does not work with m5stickc plus (adsbygoogle = window.adsbygoogle || []).push({}); ```
``` ```
``` (function() { if((".artleft pre").length > 0){ \$(".artleft pre").addClass('prettyprint linenums'); prettyPrint(); }; \$(".artleft p > code").each(function() { if (\$(this).text().length >= 30) { \$(this).addClass('linecode'); }else{} }); })(); ```
``` ```
``` © 2019 Programming tutorial for beginners ```