It is an example run for array merge algorithm described here: https://max-arbuzov.blogspot.com/2021/10/merge-sort-with-osqrtn-auxiliary-memory.html. Using that algorithm will allow to create Mergesort-based algorithm with O(sqrt(n)) additional memory usage.
The algorithm recieves two sorted sub-arrays and returns one sorted array that contains elements from sub-arrays.
The input sub-arrays and a temporary buffer:
Virtually divide the array and the buffer into pages (or sections):
Stage 1. Merge array elements into pages (pre-merging)
Definition: "Page" is a piece of the array. The synonym is "section". All pages have the same size (length) and they go sequentially without gaps or overlapping.
Definition: "Merge into a page" means to select the minimal element in sub-arrays A and B, extract (remove) it and add it into the page. And repeat this step until the page is filled or there are no more elements in A and B. To find the minimal element use the fact that both sub-arrays are sorted.
Definition: "Sequence number" or order number shows when page has been filled or the filling order, e.g. 1st, 2nd, 3rd etc. Each page will have its own sequence number after it is filled. Sequence numbers are stored in auixiliary memory.
Step 1.1. Merge into bufpage_1. This page is the 1st to be filled, so its sequence number is 1. Store the sequence number somewhere. The step and its result are below:
Step 1.2. Merge into
bufpage_2. This page is the 2nd to be filled, so its
sequence number is 2. Store the sequence number somewhere. The step and its result are below:
Step 1.3.
page_1 became free. Merge into
page_1. This page is the 3rd to be filled, so its
sequence number is 3. Store the sequence number somewhere. The step and its result are below:
Step 1.4.
page_4 became free. Merge into
page_4. This page is the 4th to be filled, so its
sequence number is 4. Store the sequence number somewhere. The step and its result are below:
Step 1.5.
page_2 and
page_5 became free. Merge into
page_2. This page is the 5th to be filled, so its
sequence number is 5. Store the sequence number somewhere. The step and its result are below:
Step 1.6.
page_5 is free. Merge into
page_5. This page is the 6th to be filled, so its
sequence number is 6. Store the sequence number somewhere. The step and its result are below:
Step 1.7.
page_6 became free. Merge into
page_6. This page is the 7th to be filled, so its
sequence number is 7. Store the sequence number somewhere. The step and its result are below:
Step 1.8. Sub-arrays
A and
B are empty now.
page_6 is the last to be filled, it is filled incompletely, move
page_6 to the end of the array (to
page_7). The step and its result are below:
Step 1.9.
page_3 and
page_6 are free. Move
bufpage_1 into
page_3 and
bufpage_2 into
page_6. Store or update sequence numbers for affected pages. The step and its result are below:
Now array elements are merged into pages (or pre-merged). The result of stage 1 is below:
Stage 2. Rearrange (or reorder) pages
Now pages are in incorrect positions, they need to be rearranged. To do it inspect all pages from page_1 to page_7 and check if they are in their correct position according to their sequence number. Move pages into their correct positions when necessary. When moving pages update sequence number of pages.
Step 2.1. Check page_1, it is in incorrect position, it should be moved to position 3. Exchange page_1 and page_3. The step and its result are below:
Step 2.2. Check
page_1 again, it is in correct position, no need to move. The result of this step is below:
Step 2.3. Check
page_2, it is in incorrect position, it should be moved to position 5. Exchange
page_2 and
page_5. The step and its result are below:
Step 2.4. Check
page_2 again, it is in incorrect position, it should be moved to position 6. Exchange
page_2 and
page_6. The step and its result are below:
Step 2.5. Check
page_2 again, it is in correct position, no need to move. The result of this step is below:
Step 2.6. Check
page_3, it is in correct position, no need to move. The result of this step is below:
Step 2.7. Check
page_4, it is in correct position, no need to move. The result of this step is below:
Step 2.8. Check
page_5, it is in correct position, no need to move. The result of this step is below:
Step 2.9. Check
page_6, it is in correct position, no need to move. The result of this step is below:
Step 2.10. Check
page_7, it is in correct position, no need to move. The result of this step is below:
Now all pages are in their correct (final) place. The result of stage 2 is below:
References.
1. Algorithm description. https://max-arbuzov.blogspot.com/2021/10/merge-sort-with-osqrtn-auxiliary-memory.html
Комментариев нет:
Отправить комментарий