The task is to implement the merge sorting algorithm, having read the implementation options on other sites and the wiki version, the implementation seemed rather cumbersome and not quite elegant, in my own version I set myself the task:
- Execute recursively.
- One function.
- Reduce the number of operands.
- Reduce the number of parameters to the pointer to the array passed to the function and the size of the array itself.
After some transformations, I reduced the code to the one below, compiled with the error "stuck overflow: access to a prohibited memory location," or "access violation during reading at the address ..".
I can’t find a leak for a long time and ask someone to notice more carefully and tell me where exactly the output goes beyond the array in this code:

void merge_sort(int* unsorted, unsigned int size) { if (size < 2) return; unsigned int middle = size >> 1; merge_sort(unsorted, middle); merge_sort(unsorted + middle, size - middle); int* first = unsorted; int* second = unsorted + middle; int* sorted = new int[size]; while (first != (unsorted + middle) && second != (unsorted + size)) *sorted++ = *first < *second ? *first++ : *second++; while (first != (unsorted + middle)) *sorted++ = *first++; while (second != (unsorted + size)) *sorted++ = *second++; sorted -= size; while (unsorted != second) *unsorted++ = *sorted++; delete[] sorted; }
  • At the moment: by finding the values ​​in the log, I found the function works correctly until the last cycle, which for some unknown reason becomes infinite ..
  • Fully working version. After just something ..
  • one
    Why size >> 1 , but not normal human size / 2 ? Where did the shift come from? - AnT
  • size >> 1 <=> size / 2^1 , which is essentially faster and there is no implicit type conversion double to int in the case of size / 2 - PostPunkTheSmith
  • Firstly, it is not at all "faster", because for unsigned int these options are absolutely strictly equivalent. Never in C / C ++ code does it make sense to manually “optimize” integer division or multiplication by a compile-time constant. And to “optimize” the division by 2 is a gross profanity. Secondly, what else is "double to int" ??? Where did you see double ??? - AnT
  • There are some wild attempts to save on variables in your code. Do not do this. Get twice as many variables with your own clear roles, and the code will become much more readable. - AnT
  • @AnT, thanks for the advice, but it won't be fair - PostPunkTheSmith

1 answer 1

  • (Already fixed.) Error in condition of first cycle

     while (first != (unsorted + middle) || second != (unsorted + size)) *sorted++ = *first < *second ? *first++ : *second++;

    will cause a flight outside the array because of || in the condition. Here, obviously, you need && , rather than || .

  • (Already fixed.) Obvious error when processing the "tail" of the array

     while (second != (unsorted + middle)) *sorted++ = *second++;

    Your second should go to unsorted + size , and not to unsorted + middle , as you yourself know perfectly well, judging by the condition of the first cycle.

  • (Already corrected.) Further, some kind of nonsense was written

     while (sorted != (sorted - size)) *(unsorted-- + size) = *sorted--;

    The condition of this loop is always true if size not equal to 0. That is, it is an infinite loop. What do you mean?

  • (Already corrected.) Your “intention” with the last cycle is understandable (although it is implemented crookedly), however, in addition to the senseless condition, it suffers from other jambs. Namely:

    • After previous cycles, the sorted pointer points to the "trash" value after the last sorted . In the last loop, your copy from *sorted-- will in the first step copy this “trash” value. Since your loop is conceived as doing exactly the right amount of iterations - size , it is clear that it will “lose” some necessary value somewhere.
    • To unsorted pointer unsorted applied -- . Who allowed you to do this? The unsorted pointer may indicate the beginning of an array. Address arithmetic in C ++ does not allow to "kick out" the pointer to the left of the beginning of the array.
  • the program crashes on exactly the first cycle, with comparison, sorry for the raw code, there is a mechanical copy-paste error in the first case where you indicated, and the "nonsense" has the following meaning: after the previous increment in the cycle, the sorted pointer points to the last element of the subarray therefore, I assign it in reverse order so as not to reassign to it the address of the first element. - PostPunkTheSmith
  • I will add that copying the second tail is superfluous, and the last while() is obviously an extremely crooked copying of elements into the original array. - Fat-Zer
  • @PostPunkTheSmith, (sorted - size) re-evaluated on each iteration of the loop. - Fat-Zer
  • one
    @PostPunkTheSmith: Implying that it is necessary to correct errors about which AnT writes, everything is as it is: only one of these two cycles is executed. And it will work. But you can get rid of the second cycle, thereby reducing the cost of copying to sorted and back. - Fat-Zer
  • one
    @ Fat-Zer: Logical. The two cycles following the main loop should copy the data directly into the unsorted array. Copy them first to sorted , and then from there to unsorted - this is a meaningless transfusion back and forth. But this is optimization. At first, it would be possible to make an existing option. - AnT