How do I correctly sort a strip of integers?-CodePudding

I have a problem. I need to write a sorting tape with limited RAM, of course I can make temporary tapes with already sorted information, but how to combine them into one tape afterwards? Is there any algorithm for this task? Here is an example of what I want to get:

RAM holds only 4 items

8 7 6 5 4 3 2 1 <- initial row on tape

read and sort 4 items:

5 6 7 8 <- tmp tape1
4 3 2 1 <- initial tape

read and sort 4 items:

5 6 7 8 <- tmp tape1
1 2 3 4 <- tmp tape

merge 2 tmp tapes:

1 2 3 4 5 6 7 8 <- output tape

P.S

You can do the following operations with the tape: read a cell, write to a cell, move it back and forth

CodePudding user response：

Guessing at the operations, I would put all entries on each tape. I would also organize RAM into a heap and go back and forth.

So you start with

8 7 6 5 4 3 2 1

Now work left to right. Load up 4 elements in a heap and keep writing out the smallest as you go. This gives you:

5 4 3 2 1 6 7 8

Now go right to left writing out the largest. This gives you:

1 2 3 5 4 6 7 8

Now left to right getting:

1 2 3 4 5 6 7 8

And we're done.

CodePudding user response：

The simplest way to do merge sorting is to merge in pairs. That is, given 8 items that you want to sort, you start by merging 2-element blocks. So, for example, your original tape might contain:

7,3,6,8,4,1,5,2

Go through and merge 2-element blocks, writing temporary tapes for each block. That is:

Merge 7 and 3, and write a temporary tape that contains [3,7]
Merge 6 and 8, and write temporary tape [6,8]
Merge 4 and 1, and write temporary tape [1,4]
Merge 5 and 2, and write temporary tape [2,5]

Now you have four temporary tapes that contain 2-element sorted sequences. Repeat the process, merging those 2-element sequences.

Merge [3,7] with [6,8] to produce [3,6,7,8]
Merge [1,4] with [2,5] to produce [1,2,4,5]

And, finally, merge those 4-element sequences:

Merge [3,6,7,8] with [1,2,4,5] to produce [1,2,3,4,5,6,7,8]

The above can be implemented with a minimal amount of extra memory. The heap solution will be faster if you have the memory for it, but it's a little bit more involved.