MergeSort space complexity

[ERGeorgiev]

Describe the bug
The MergeSorter describes its space complexity as "space complexity: O(n)," in the comment above, but to me it seems more like it's O(n log n), as the code is creating new arrays with the same amount of data as the initial array on each split level. So N being the size of the initial array, multipled by log N for each split level.

[siriak]

Hi, while your calculation is correct, all those arrays don't exist at the same time. They are created and destroyed as algorithm executes and at any given moment there is no more than 2n additional memory used. Hence the O(n) complexity. You can find a good explanation here https://www.reddit.com/r/learnprogramming/comments/k9w152/algorithms_why_is_merge_sorts_space_complexity_on/

[ERGeorgiev]

Ah I understand now, thanks.