FANDOM


QuestionEdit

Write an implementation of Mergesort, in Java, to sort a primitive array of integers.

  1. Is mergesort stable?
  2. What is the time complexity?
  3. Is this implementation in-place?

AnswerEdit

(written on paper and retyped here, hasn't been checked with a compiler yet)

// mergesort, recursive
public static int[] mergesort(int[] x) {
    if (x.length < 2) {
        return x;
    } else {
        // +1 so left half is bigger if x.length is an odd number
        int half = (x.length + 1) / 2;
 
        int[] left = new int[half];
        int[] right = new int[x.length - half];
 
        // copy left half
        for (int i = 0; i < half; i++) {
            left[i] = x[i];
        }
 
        // copy right half
        for (int i = half; i < x.length; i++) {
            right[i - half] = x[i];
        }
 
        // recursively create left and right halves
        // then merge the sorted left and right halves
        return merge(mergesort(a), mergesort(b));
    }
}
 
// merges two sorted sublists
public static int[] merge(int[] left, int[] right) {
    int[] result = new int[left.length + right.length];
    int i = 0;
    int j = 0;
 
    // merge left and right halves together
    while (i + j < left.length + right.length) {
        if (i < left.length && j < right.length) {
            if (left[i] > right[j]) {
                result[i + j] = right[j];
                j++;
            } else {
                result[i + j] = left[i];
                i++;
            }
        } else if (i < left.length) {
            result[i + j] = left[i];
            i++;
        } else {
            result[i + j] = right[j];
            j++;
        }
    }
 
    return result;
}

OtherEdit

  1. Yes, mergesort is a stable sort.
  2. The time complexity of mergesort is O(nlogn), where n is the number of items to be sorted. This value is calculated by solving the recurrence relation: T(n) = 2T(n) + n where T(n) is the amount of time required to merge sort a list of size n.
  3. No.

CompiledEdit

Here's a complete Java program that has a Merge class which implements merge sort on a primitive array of a generic type T which implements the Comparable interface.

This improves upon the implementation given above in two ways:

  • Can sort any type that implements Comparable, not just ints
  • Space complexity in this version is O(n) as only a single extra array is used (declared in the public driver). The version above has log(N) different arrays existing simultaneously, as the array is unfortunately declared locally in the recursive method.

The output of the program is the original array followed by the sorted array.

{z, x, a, a, b, w, s, r, i, k, j, e, f, g, s, s, t, a, b, d}
{a, a, a, b, b, d, e, f, g, i, j, k, r, s, s, s, t, w, x, z}


public class Merge<T extends Comparable<T>> {
	T[] data;
 
	// main()
	public static void main(String[] args) {
		String[] x = {"z", "x", "a", "a", "b", "w", "s", "r", "i", "k", "j", "e", "f", "g", "s", "s", "t", "a", "b", "d"};
		Merge<String> obj = new Merge<String>(x);
		obj.print();
		obj.mergeSort();
		obj.print();
	}
 
	// constructor
	public Merge(T[] data) {
		this.data = data;
	}
 
	// public driver for merge sort
	public void mergeSort() {
		if (this.data != null) {
			T[] temp = (T[]) new Comparable[this.data.length];
			mergeSort(this.data, temp, 0, this.data.length - 1);
		}
	}
 
	// prints the array
	public void print() {
		if (data == null) {
			System.out.println("null");
		} else if (data.length == 0) {
			System.out.println("{}");
		} else {
			String result = "{" + data[0];
			for (int i = 1; i < data.length; i++) {
				result += ", " + data[i];
			}
			result += "}";
			System.out.println(result);
		}
	}
 
	// internal recursive sort
	private void mergeSort(T[] data, T[] temp, int left, int right) {
		if (left < right) {
			int half = left + (right - left) / 2;
			mergeSort(data, temp, left, half);
			mergeSort(data, temp, half + 1, right);
			merge(data, temp, left, half, half + 1, right);
		}
	}
 
	// internal, merges two sublists
	private void merge(T[] data, T[] temp, int leftS, int leftE, int rightS, int rightE) {
		int i = leftS;
		int count = 0;
		int j = rightS;
 
		// compare data[i], data[j] and put smaller into its final position
		do {
			if (data[i].compareTo(data[j]) <= 0) {
				temp[leftS + count++] = data[i++];
			} else {
				temp[leftS + count++] = data[j++];
			}
		} while (i <= leftE && j <= rightE);
 
		// copy remaining portion of list
		if (i > leftE) {
			for (i = j; i <= rightE; i++) {
				temp[leftS + count++] = data[i];
			}
		} else {
			for (j = i; j <= leftE; j++) {
				temp[leftS + count++] = data[j];
			}
		}
 
		// copy temp back to original array
		for (i = leftS; i <= rightE; i++) {
			data[i] = temp[i];
		}
	}
}

Sketch of time complexity proofEdit

  1. Begin with the recurrence relation T(N) = 2T(N/2) + N (where T(1) = 1), because mergesort cuts the amount of work in half at each recursive call, followed by linear time to merge the sorted sublists.
  2. Divide the recurrence relation by N
  3. Assume N = 2^k for some integer k. That is, we only allow N to be a power of 2.
  4. Write out the sequence of recurrence relations for all N = 2^k
  5. Add up the sequence of equations. A lot of cancellation occurs. Result will be T(N)/N = T(1)/1 + log(N) because there are log(N) equations.
  6. Multiply through by N and O(Nlog(N)) run time is apparent.

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.