mergesort - Merge sort in java and copying array, still nlogn? -

i've taken @ few implementations of merge sort in java, , seems splitting part commonly done creating 2 new arrays, left , right , copying left , right parts arrays respectively.

my question is: still gives nlogn time right? because each split have n+n time (n time splitting array, n time merging array) , there logn splits, have 2nlogn still nlogn. correct?

which implementations looking at? primary sorting algorithms used jdk dualpivotquicksort (for primitive arrays), timsort , comparabletimsort (for object arrays/collections), , incomprehensible wizardy in arraysparallelsorthelpers concurrent sorts.

all of these classes provide highly-tuned implementations of quicksort or mergesort (or in parallel case "cilksort", sounds concurrency-friendly mergesort). these algorithms o(n log(n)) - it's impossible better o(n log(n)) without additional constraints on inputs.

as whether these algorithms spend o(n) time copying values back-and-forth between temporary storage, it's case-by-case question. possible these implementations try avoid using o(n) memory , time linear copying, oftentimes such work not bottleneck. example cilksort uses secondary "workspace array" copy values , forth in successive stages, makes easier enforce invariants since "prior" stage in reliable state. implementations try avoid unnecessary array-copies whenever possible.

at public api level we'll notice collections.sort() calls .toarray(), sorts array, , copies values original list. practical optimization - it's faster sort array , 2 linear copies deal method invocations (and potentially inefficient list implementations, such linkedlist) of modifying list in-place.