[edtechre]

The recursive merge sort is not quite correct:

function mergeSort(items){

    if (items.length == 1) {
        return items;
    }

    var middle = Math.floor(items.length / 2),
        left = items.slice(0, middle),
        right = items.slice(middle);

    return merge(mergeSort(left), mergeSort(right));

}

You don't need to run merge on the left and right partitions every call. You only need to do that if the left partition's last element is greater than the right partition's first element. Otherwise, you can just append the right partition to the left, since they are already in sorted order.

[jules]

Why does that make the algorithm incorrect? At most your method might be faster, although I doubt it because the probability that the left's last is greater than the right's first is small and gets exponentially smaller as the length of the sequences you're merging increases.

[edtechre]

It /might/ be faster? What? Do you fully understand the invariant of the algorithm? The left should always be less than the right partition. There's no need to re-merge them each call. As it is, you are always comparing all elements in the left and right partitions with the merge when you don't have to!

[jules]

I believe you're confused between mergesort and quicksort. Can you post the code how you'd code mergesort?

[edtechre]

Nope. What I said is still true. Here is my code in Java:

public List<Integer> mergeSort(List<Integer> list) { // Base case // If list has one (or less) element, return list as is int size = list.size(); if (size <= 1) { return list; }

		// Partition list in half
		int m = size / 2;
		List<Integer> left = new ArrayList<Integer>();
		List<Integer> right = new ArrayList<Integer>();
		for (int i = 0; i < m; i++) {
			left.add(list.get(i));
		}
		for (int i = m; i < size; i++) {
			right.add(list.get(i));
		}
		
		// Recursively merge sort each partition
		left = mergeSort(left);
		right = mergeSort(right);
		
		// If the last element of the left partition is greater than the first element of the right partition
		// The left and right partitions need to be rearranged
		if (left.get(left.size() - 1) > right.get(0)) {
			return merge(left, right);
		// Otherwise left and right partitions are in the correct order
		} else {
			left.addAll(right);
			return left;
		}
	}
	
	protected List<Integer> merge(List<Integer> left, List<Integer> right) {
		List<Integer> result = new ArrayList<Integer>();
		// While both containers are non-empty
		// Move lesser elements to the front of the result, and remove them from their containers
		while (!left.isEmpty() && !right.isEmpty()) {
			if (left.get(0) < right.get(0)) {
				result.add(left.remove(0));
			} else {
				result.add(right.remove(0));
			}
		}
		// The container that still has elements contains elements greater than those in the other container
		// It is assumed that the elements in the container are also already sorted
		// So the non-empty container's elements should be appended to the end of the list
		if (!left.isEmpty()) {
			result.addAll(left);
		} else {
			result.addAll(right);
		}
		return result;
	}

[jules]

That's what I'm saying. It's a minor optimization of the mergesort algorithm, and it's not the usual way that mergesort is presented. And I'm skeptical that it's really an optimization. Have you benchmarked it?

This condition is going to be true most of the time:

    left.get(left.size() - 1) > right.get(0)

As the lists get longer (where this optimization could pay off), the condition is more and more likely to be true.

For the case of nearly sorted lists, it could be an important optimization. But to say that the original mergesort is incorrect is not true.