Merge Sort

1. Merge Sort Algorithm and its Fundamental Steps

Page 198

Merge Sort is a prime example of the Divide-and-Conquer algorithm design technique. It sorts a given array by following a three-step process:

• Divide: The algorithm starts by dividing the original array A[0..n-1] into two approximately equal halves: A[0..⌊n/2⌋ - 1] and A[⌊n/2⌋..n-1]. This division continues recursively until subproblem arrays has a single element, which are considered inherently sorted.

• Conquer (Solve): Each of these subproblems (the two halves) is then sorted recursively using Merge Sort itself. This recursive sorting continues until the subarrays consist of a single element, which is considered sorted by definition.

• Combine: After the subproblems are sorted, the solutions to these smaller sorted halves are combined (merged) to produce a single sorted array. This is done by comparing elements from the two sorted subarrays and adding the smaller element to a new array, repeatedly, until all elements are merged.

2. Algorithm (Pseudocode) for Merge Sort

The Mergesort algorithm works by recursively dividing an input array into two halves, sorting each half, and then merging the two sorted halves back into a single sorted array.

Algorithm Mergesort(A[0..n-1]):
// Sorts array A[0..n-1] in nondecreasing order
// Input: An array A[0..n-1] of orderable elements
// Output: Array A[0..n-1] sorted in nondecreasing order

if n > 1 then
    // Divides the input array A into two halves, B and C.
    p <- ceil(n / 2)
    Let B[0..p-1] <- A[0..p-1]    // Copy first p elements to B
    Let C[0..p-1] <- A[p..n-1]    // remaining n-p elements to C

    // Recursively sorts the two smaller arrays, B and C.
    Mergesort(B[0..p-1])
    Mergesort(C[0..p-1])

    // Combine
    Merge(B, C, A)

return A

Algorithm Merge(B[0..p-1], C[0..q-1], A[0..p+q-1]):

// Merges two sorted arrays B (of size p) and C (of size q) into sorted array A
// Input: Arrays B[0..p-1] and C[0..q-1] both sorted in nondecreasing order
// Output: Sorted array A[0..p+q-1] containing all elements from B and C

i <- 0    // Index for array B, initialized to its first element
j <- 0    // Index for array C, initialized to its first element
k <- 0    // Index for array A, where merged elements are placed

// Compare elements from B and C, placing the smaller one into A
while i < p AND j < q do
	if B[i] <= C[j] then
		A[k] <- B[i]
		i <- i + 1
	else
		A[k] <- C[j]
		j <- j + 1
	k <- k + 1

if i = p then     // If all elements from B have been copied
	copy C[j..q-1] into A[k..p+q-1]
else               // If all elements from C have been copied
	copy B[i..p-1] into A[k..p+q-1]

The overall time efficiency of Mergesort is Θ(n log n) in all cases (worst, average, and best), making it a very efficient sorting algorithm. Its primary drawback is the requirement for linear extra storage for the temporary arrays B and C during the merging process.

3. Time Complexity Analysis of Merge Sort

The efficiency of Merge Sort is typically analyzed using a recurrence relation derived from its divide-and-conquer structure.

Assuming the input size n is a power of 2 for simplicity, the recurrence relation for the number of key comparisons C(n) is:

C(n) = 2C(n/2) + Cmerge(n) for n > 1, with C(1) = 0.

Here:

• 2C(n/2) represents the cost of recursively sorting the two halves of the array.
• Cmerge(n) represents the cost of merging the two sorted halves.

In the worst case, Cmerge(n) (the number of key comparisons during the merging stage) is n - 1. This occurs when elements from the two arrays B and C alternate in such a way that neither array becomes empty until the other has only one element left.

Substituting this into the recurrence, we get the worst-case recurrence relation:

Cworst(n) = 2Cworst(n/2) + n - 1 for n > 1, Cworst(1) = 0.

This recurrence can be solved using the Master Theorem.

For a recurrence of the form T(n) = aT(n/b) + f(n), where a=2, b=2, and f(n) = n-1 (which is Θ(n^d) with d=1):

• Since a = b^d (2 = 2^1), the second case of the Master Theorem applies.

Therefore, the time efficiency of Merge Sort in the worst case is Θ(n log n).

Specifically, for n = 2^k, the exact solution to the worst-case recurrence is:

Cworst(n) = n log₂ n − n + 1

The number of key comparisons for Merge Sort in the average case is also in Θ(n log n), being about 0.25n less than the worst case for large n.

4. Is Merge Sort In-place? Is it Stable?

In-place sorting algorithm?

An algorithm is considered "in-place" if it does not require extra memory, except possibly for a few memory units. Merge Sort is not an in-place sorting algorithm in its typical implementation. Its principal shortcoming is the linear amount of extra storage (auxiliary memory) it requires.

This is because the Merge function usually needs temporary arrays (like B and C in the pseudocode) to hold the two halves before merging them back into the original array A. While merging can theoretically be done in-place, the resulting algorithm becomes significantly more complicated and is primarily of theoretical interest.

Stable sorting algorithm? Merge Sort is a stable sorting algorithm. A sorting algorithm is stable if it preserves the relative order of any two equal elements in its input.

For example, if an input list contains two equal elements, A[i] and A[j], where i < j, then in the sorted list, they will remain in positions i' and j' such that i' < j'.

Merge Sort achieves stability because its Merge procedure, when encountering equal elements from the two halves B and C, consistently copies the element from the left subarray (B) first (e.g., if B[i] ≤ C[j] A[k] ← B[i]). This ensures that the original relative order of equal elements is maintained.