Notice that as soon as the first record is written to an output tape, the memory it used becomes available for another record. Assume that we are sorting in ascending order, if the next record is not smaller than the record we have just output, then it can be included in the run.
Initialize arrays memo, tmp, and scan Initialize pointers memo_tail, tmp_tail, scan_tail, and scan_head
Read input: n, m Read the input sequence into the scan array
while scan_tail is not equal to 0: if scan_tail is less than m - 1: Set memo_tail to 1 while scan_head is not equal to scan_tail: x = scan[scan_head] Increment scan_head memo[memo_tail] = x Increment memo_tail Sort memo[1] to memo[memo_tail-1] else: for i from 1 to m: x = scan[scan_head] Increment scan_head memo[i] = x Set memo_tail to m + 1 Sort memo[1] to memo[m]
Remove the first element from the scan array lst = memo[1] while scan_head is not equal to scan_tail: x = scan[scan_head] Increment scan_head if x is less than lst: tmp[tmp_tail] = x Increment tmp_tail else: Insert x into the memo array lst = memo[1] Remove the first element from memo Increment memo_tail
Reset scan_head and scan_tail pointers while memo_tail is not equal to 1: Remove the first element from memo Print a newline character for i from 0 to tmp_tail-1: scan[scan_tail] = tmp[i] Increment scan_tail Reset tmp_tail pointer
Return 0
Function insert(x): i = memo_tail Increment memo_tail while i / 2 > 0 and memo[i / 2] > x: memo[i] = memo[i / 2] i = i / 2 memo[i] = x
Function delete(flg): if flg equals 1: Print memo[1] else: Print " " + memo[1] child = 2 par = 1 while child <= memo_tail - 1: if child < memo_tail - 1 and memo[child + 1] < memo[child]: child = child + 1 memo[par] = memo[child] par = child child = par * 2 memo[par] = memo[memo_tail - 1] Decrement memo_tail
Chapter 3: Testing Results
input
expect
aim
output
13 3 81 94 11 96 12 99 17 35 28 58 41 75 15
11 81 94 96 99 12 17 28 35 41 58 75 15
sample
11 81 94 96 99 12 17 28 35 41 58 75 15
Chapter 4: Analysis and Comments
Time Complexity Derivation:
Initialization: This is a constant time operation, O(1), as it involves setting up pointers and arrays.
Reading Input: Reading n and m is O(1), but reading the input sequence into the scan array is O(n), where n is the length of the input sequence.
Main Loop:
The main loop runs until scan_tail is not equal to 0. The number of iterations of this loop depends on the input size, but let’s assume it runs k times.
Inside the loop, there are several operations:
Sorting memo: If we assume a simple comparison-based sort like quicksort or mergesort, the sorting operation would have a time complexity of O(m log m), where m is the size of the memo array.
Inserting elements into memo: The insert function likely has a complexity of O(log m) due to the binary heap structure.
Deleting elements from memo: The delete function also likely has a complexity of O(log m) for similar reasons.
Assuming the sorting is the dominant factor, the time complexity inside the loop is O(m log m). Since the loop runs k times, the overall complexity of the loop is O(k * m log m).
Resetting Pointers and Printing: These are constant time operations, O(1).
Total Time Complexity: The total time complexity is the sum of all the individual complexities. Assuming k is proportional to n (the size of the input), the total time complexity is O(n + k * m log m). If k is approximately n, this simplifies to O(n * m log m).
Derivation of space complexity:
Input Array scan: This array holds the input sequence and has a space complexity of O(n).
Memoization Array memo: This array is used to store elements and sort them. Its size is based on m, so it has a space complexity of O(m).
Temporary Array tmp: This array is used to store elements temporarily and has a space complexity of O(m).
Pointers: The pointers used in the program are constant space, O(1).
Total Space Complexity: The total space complexity is the sum of the spaces used by the arrays. Therefore, the total space complexity is O(n + m + m) = O(n + 2m), which simplifies to O(n + m) if m is considered a constant or if it grows with n.
