%sorts the values array using a recursive merge sort
function output=mergesort(values)
  valuesLength = length(values);
  if valuesLength <= 1
    output = values;
  else
    valuesMiddle = floor(valuesLength / 2);
    left = mergesort(values(1:valuesMiddle));
    right = mergesort(values(valuesMiddle+1:valuesLength));
    rightLength = valuesLength - valuesMiddle;

    %merge the two sorted arrays
    leftIndex = 1;
    rightIndex = 1;
    output = zeros(1, valuesLength);
    for i = 1 : valuesLength
      if leftIndex <= valuesMiddle && (rightIndex > rightLength || left(leftIndex) <= right(rightIndex))
        output(i) = left(leftIndex);
        leftIndex = leftIndex + 1;
      else
        output(i) = right(rightIndex);
        rightIndex = rightIndex + 1;
      end
    end
  end
