Is the correct algorithm for a balanced merge sort? (We have a sequence of numbers 1-8 3 7 4 11 -0 13 -2 6

  1. read the first 4 numbers
    • a1 <a2 <a3 <a4? not [],[],[],[];
    • a1 <a2 <a3? not [],[],[],[];
    • a1 <a2? not [],[],[],[];
    • [one'],[],[],[];
    • a2 <a3 <a4? no [1 '], [], [], [];
    • a2 <a3? no [1 '], [], [], [];
    • [1 '], [- 8'], [], [];
    • a3 <a4? yes [1 '], [- 8'], [3,7 '], [];
  2. The following 4 numbers

    1 answer 1

    So - by dividing by approximately in half, until you get a pair of numbers. Then the process goes back. The balance is expressed in the fact that the sizes of groups differ by no more than 1. Merging is performed by alternately taking the first two numbers from the two groups, comparing them and transferring them to the resulting set of the smaller number.

    1 -8 3 7 4 11 0 13 -2 6 1 -8 3 7 4 | 11 0 13 -2 6 | | 1 -8 3 | 7 4 | 11 0 13 | -2 6 | | 1 -8 | 3 | 4 7 | 11 0 | 13 | -2 6 | | | | | -8 1 | 3 | 4 7 | 0 11 | 13 | -2 6 | | | -8 1 3 | 4 7 | 0 11 13 | -2 6 | -8 1 3 4 7 | -2 0 6 11 13 -8 -2 0 1 3 4 6 7 11 13
    • How do we know where half is if we work with a txt file and ifstream? - dahbka
    • @dahbka In the condition of this was not. But, I think, for example, if the file allows you to stuff everything into memory, then in memory. If not, then we divide, for example, all the even entries in one file, the odd ones in the second. And we recursively work with the halves, and then merge them - it’s really easy to merge something from the files .. - Harry
    • Thanks, but what is the practical use of balanced sorting? - dahbka
    • Sort :) He has guaranteed performance O(N*log N) , while allowing you to work with files. - Harry