The numbers in the output below
were randomly generated.
The numbers you get will be different.
That's fine.
Return to
assignment description
Sample Output
Modified Merge Sort
-------------------
This program demonstrates a version of merge sort that takes advantage of
existing "runs" of sorted datain the array. It finds all such runs in the
original array, then merges consecutive runs together. The process repeats
until there is only one run left in the array.
Original Program: Mark Young (A00000000)
Completed by: ____ _____ (A00______)
...Press ENTER...
How long should I make the list? 16
Array values before sorting:
458 325 202 891 340 66 764 851
383 27 399 125 441 621 180 194
...Press ENTER...
Here are the runs found in the array:
Run 0:
458 ... ... ... ... ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 1:
... 325 ... ... ... ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 2:
... ... 202 891 ... ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 3:
... ... ... ... 340 ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 4:
... ... ... ... ... 66 764 851
... ... ... ... ... ... ... ...
...Press ENTER...
Run 5:
... ... ... ... ... ... ... ...
383 ... ... ... ... ... ... ...
...Press ENTER...
Run 6:
... ... ... ... ... ... ... ...
... 27 399 ... ... ... ... ...
...Press ENTER...
Run 7:
... ... ... ... ... ... ... ...
... ... ... 125 441 621 ... ...
...Press ENTER...
Run 8:
... ... ... ... ... ... ... ...
... ... ... ... ... ... 180 194
...Press ENTER...
Merging 0 and 1
Yields:
325 458 ... ... ... ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Merging 2 and 3
Yields:
... ... 202 340 891 ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Merging 4 and 5
Yields:
... ... ... ... ... 66 383 764
851 ... ... ... ... ... ... ...
...Press ENTER...
Merging 6 and 7
Yields:
... ... ... ... ... ... ... ...
... 27 125 399 441 621 ... ...
...Press ENTER...
Here are the runs found in the array:
Run 0:
325 458 ... ... ... ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 1:
... ... 202 340 891 ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 2:
... ... ... ... ... 66 383 764
851 ... ... ... ... ... ... ...
...Press ENTER...
Run 3:
... ... ... ... ... ... ... ...
... 27 125 399 441 621 ... ...
...Press ENTER...
Run 4:
... ... ... ... ... ... ... ...
... ... ... ... ... ... 180 194
...Press ENTER...
Merging 0 and 1
Yields:
202 325 340 458 891 ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Merging 2 and 3
Yields:
... ... ... ... ... 27 66 125
383 399 441 621 764 851 ... ...
...Press ENTER...
Here are the runs found in the array:
Run 0:
202 325 340 458 891 ... ... ...
... ... ... ... ... ... ... ...
...Press ENTER...
Run 1:
... ... ... ... ... 27 66 125
383 399 441 621 764 851 ... ...
...Press ENTER...
Run 2:
... ... ... ... ... ... ... ...
... ... ... ... ... ... 180 194
...Press ENTER...
Merging 0 and 1
Yields:
27 66 125 202 325 340 383 399
441 458 621 764 851 891 ... ...
...Press ENTER...
Here are the runs found in the array:
Run 0:
27 66 125 202 325 340 383 399
441 458 621 764 851 891 ... ...
...Press ENTER...
Run 1:
... ... ... ... ... ... ... ...
... ... ... ... ... ... 180 194
...Press ENTER...
Merging 0 and 1
Yields:
27 66 125 180 194 202 325 340
383 399 441 458 621 764 851 891
...Press ENTER...
Array values after sorting:
27 66 125 180 194 202 325 340
383 399 441 458 621 764 851 891
...Press ENTER...
Return to
assignment description