Answer to Question #262727 in Algorithms for Shadow

Question

3. In computer science, a sorting algorithm is an algorithm that puts elements of a list in a

certain order. The most frequently used orders are numerical order and lexicographical

order.

I. Sort the [19, 7, 43, 3, 9, 82, 10] array using merge sort algorithm. Note that the

illustrations and labels are mandatory.

II. Write pseudo/source codes to merge [2, 4, 8, 9] and [3, 5, 6, 10] arrays into a

single sorted array. 

III. Estimate the time complexity of merge sort algorithm showing the steps you followed including reduction.

Answer 1

I

II

Code in Python

# Lists to merge
L1 = [2, 4, 8, 9]
L2 = [3, 5, 6, 10]
# Get their length
n1 = len(L1)
n2 = len(L2)
# Indexes
i1 = 0
i2 = 0
i = 0
# Resulting array of size (n1+n2)
L = [0] * (n1 + n2)
while i1 < n1 and i2 < n2:
    if L1[i1] < L2[i2]:
        L[i] = L1[i1]
        # increment indexes
        i += 1
        i1 += 1
    else:
        L[i] = L2[i2]
        # increment indexes
        i += 1
        i2 += 1
if i1 < n1:
    # Add rest of L1
    for ii in range(i1, n1):
        L[i] = L1[ii]
        i += 1
if i2 < n2:
    # Add rest of L2
    for ii in range(i2, n1):
        L[i] = L2[ii]
        i += 1


print(L)

III

In each divide step, we get arrays at most half of the source array size, so there should be no more than log₂(n) divide and merge steps. Each divide step takes a constant amount of operation, independent of the array size, while the merge step needs to check every from the n values. So total time complexity of the sort algorithm is O(n log(n))