Since arrays are passed by reference in C++ does the space complexity of merge sort (recursive) still remain O(n) ? If yes then why? (I argue that since elements of the array are not being copied so the space complexity should be constant, i.e. , O(k).)
Asked
Active
Viewed 275 times
-2
-
Where did you learn that arrays are passed by reference? – NathanOliver Jan 04 '17 at 18:12
-
@NathanOliver By default c++ passes arrays by reference – Tanmay Bhatnagar Jan 04 '17 at 18:15
-
That is not true. By default when an aray is passed to a function a pointer to the first element of the array is passed. To pass an array by reference you would have something like `void foo(int (&arr)[10])` – NathanOliver Jan 04 '17 at 18:17
-
I understand your point but the fact remains that no extra memory is allocated so can we say that for c++ the space complexity of merge sort is constant? – Tanmay Bhatnagar Jan 04 '17 at 18:19
-
Having in-place merge sort is possible but complicated: http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm . However, it has nothing to do with C++ array passing. In general, when analyzing algorithms, it is always assumed that data is passed "by reference", not copied in O(N). – hyde Jan 04 '17 at 18:30
1 Answers
1
Space complexity remains O(n) independently on array argument calling method - it is size of buffer needed for (classic) merge sort implementation.
So you have input array (it is usually also output array) and buffer array of the same size - that is why additional space is O(n)
MBo
- 77,366
- 5
- 53
- 86
-
[link](http://quiz.geeksforgeeks.org/merge-sort/) Here in the C++ code the buffer array is 'int arr[]' in the merge function. But since the data is being passed by reference it doesnt take any extra space apart from the pointer 'arr' itself. So how is the space complexity O(n) – Tanmay Bhatnagar Jan 04 '17 at 18:40
-
1You forgot about internal buffer arrays: `/* create temp arrays */ int L[n1], R[n2];` – MBo Jan 04 '17 at 18:47