# Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort log n times. mergeRoutine is a tail call, and it doesn't add to the call stack.

The extra space I need equals to n + log n. How can the extra space be O(n)?

I think we just consider log n negligible.

public class MergeSort {

private int[] array;
private int[] helper;

public MergeSort() {
this.array = array;
this.helper = new int[array.length];
}

public void sort() {
sort(0, array.length - 1);
}

private void sort(int start, int end) {
if (end > start) {
int middle = (start + end) / 2;
sort(start, middle);
sort(middle + 1, end);
mergeRoutine(start, middle, end);
}
}

private void mergeRoutine(int start, int middle, int end) {
for (int i = start; i <= end; i++) {
helper[i] = array[i];
}
int k = start;
int i = start;
int j = middle + 1;
while (i <= middle && j <= end) {
if (helper[i] <= helper[j]) {
array[k] = helper[i];
i++;
} else {
array[k] = helper[j];
j++;
}
k++;
}

// Copy the rest. Either of the while loops works, not both.
while (i <= middle) {
array[k] = helper[i];
i++;
k++;
}
}
}


## marked as duplicate by D.W.♦, Raphael♦Jul 7 '15 at 5:52

$O(n)$ denotes the set of all functions $f(n)$ that are, for sufficiently large $n$, at most a constant factor larger than $n$. The notation $f(n) = O(n)$ is confusing because it really means $f(n) \in O(n)$.
E.g. $2n+5 \in O(n)$, $n/2 \in O(n)$, $\sqrt{n} \in O(n)$, $n + log\ n \in O(n)$ (the latter, because indeed $log\ n$ is negligible compared to $n$, e.g. $n + log\ n < 2n$ and $2n \in O(n)$).
However, $n^2 \notin O(n)$ because there's no constant $k$ that can make $n^2 < k n$ for all sufficiently large $n$.