1

I am trying doing a homework problem and I got to use the text book merge sort method and implement it into my program. I cant get it to work when I try to Dynamically allocates temporary array for merged numbers.

void Merge(int *numbers, int i, int j, int k)
{
int mergedSize = k - i + 1;         
int merge2 = k - j;
int mergePos = 0;                       
int leftPos = 0;                       
int rightPos = 0;                     
int mergedNumbers = new int[mergedSize];    
leftPos = i;                        
rightPos = j + 1;

I get a int error saying I cannot initalize an entity of type int in "int mergedNumbers = new int[mergedSize];". How can I fix this to get it work.

Alpha
  • 67
  • 1
  • 5

1 Answers1

2

new returns a pointer to the first element of the allocated array. You are trying to assign it to an int, which is not a pointer.

You should assign the result of the new expression to a pointer to int:

int* mergedNumbers = new int[mergedSize];

or more easily, you can let the compiler determine the type, so you don't have to type it twice:

auto mergedNumbers = new int[mergedSize];

Note however that mergedNumbers is a pointer in either case and must be used as such, (e.g. with the array index syntax).

Don't forget to delete[] the pointer when you don't need the allocated array anymore, otherwise you are leaking that memory:

delete[] mergedNumbers;

However, one would not use manual dynamic memory for a temporary array of dynamic size, one would use std::vector<int> instead. Using new/delete for something like this is bad style because it is prone to errors, not exception-safe and not following one of the fundamental concepts of C++ programming style known as Resource Acquisition Is Initialization (RAII)

std::vector<int> mergedNumbers(mergedSize);

Use that if you can (requires #include<vector>). If your instructor doesn't allow it, that would be very unfortunate because it would be teaching you a bad C++ style that isn't used in practice.

walnut
  • 21,629
  • 4
  • 23
  • 59
  • 1
    As an alternative, I don't see an issue with a one time allocation of a working array the same size as the array to be sorted, as both would normally be allocated and deleted in the same manner. Then references (pointers) to both arrays would be included as parameters for mergesort() and merge(). Another alternative would be std::array, but I don't know if there's an advantage to using std::array versus std::vector. – rcgldr Dec 03 '19 at 19:45
  • 1
    @rcgldr You mean that basically the caller provides the temporary array? I guess that makes sense in some special situations where the caller needs control over how memory is allocated, but in most cases the caller doesn't care whether the sort function allocates. It is also somewhat dangerous because the caller needs to guarantee matching sizes. I would at most use that as optional feature. I don't know which functions you are referring to, there is only `Merge` in the question. – walnut Dec 03 '19 at 19:56
  • 1
    @rcgldr `std::array` requires compile-time known size. If this function is supposed to sort arbitrarily sized arrays, then `std::vector` is the way to go. It is effectively equal to a raw allocation in performance when used with fixed size, but offers guaranteed correct deletion even if exceptions are thrown and always provides the correct size with `.size()` and behaves as one would except when copied or passed around (while raw arrays don't). – walnut Dec 03 '19 at 20:00
  • 1
    I forgot that std::array had a compile time size, but I don't see an issue with a caller provided temporary array, Looking at Visual Studio 2015 code for std::stable_sort, it does a one time allocation of an internal container for half of the input container size; | _Iter_diff_t<_BidIt> _Count = _STD distance(_First, _Last); | _Temp_iterator<_Iter_value_t<_BidIt>> _Tempbuf((_Count + 1) / 2); | . The members of the container include _First(), _Last(), _Maxlen(). std::stable_partition allocates a whole container | ... _Tempbuf(_Count ); | . – rcgldr Dec 03 '19 at 22:49
  • 1
    @rcgldr I think there was a misunderstanding. I don't have any problem with that. My understanding was that you were referring to the caller of the algorithm itself, i.e. the user of `std::stable_sort` providing the temporary buffer. There is good reason to allocate the buffer only once and I didn't mean to say that this was a problem. – walnut Dec 04 '19 at 01:36
  • It seems (I only have access to the [github version](https://github.com/microsoft/STL/blob/master/stl/inc/algorithm)) that the buffer is encapsulated correctly in a class, making it compliant with RAII principles and exception-safe and it also seems to contain its own size, so my concern about size mismatch does not apply either. The problems are raw `new`/`delete` with the `delete` not encapsulated in a destructor and raw pointers without accompanying size information. – walnut Dec 04 '19 at 01:39
  • A bit off topic, but Visual Studio's implementation of std::stable_sort() is not exception safe. If a user supplied compare function throws an exception, then part of the caller's container may end up in the temporary buffer and there's no code to recover the data. To be exception safe, all of the data in the container should be preserved, although reordered due to partial sorting. – rcgldr Dec 04 '19 at 03:34
  • @rcgldr I don't think it needs to provide such a level of safety. I was more thinking about not leaking memory and leaving the elements in the range in valid states, which I assume the implementation does? Because otherwise using a throwing Compare would not really be safe in any situation. Although I am not really sure how strong the exception guarantees for `std::stable_sort` and the other algorithms really are required to be. There is nothing about it in the section in the standard. – walnut Dec 04 '19 at 04:23
  • Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/203568/discussion-between-rcgldr-and-walnut). – rcgldr Dec 04 '19 at 05:57