Thread: My merge sort has a bad alloc error

  1. #1
    Registered User
    Join Date
    Feb 2016
    Posts
    6

    My merge sort has a bad alloc error

    Hello, I'm having a problem with a C++ merge sort I implemented. I'm still fairly new to the language and I don't really know about memory management as much as I'd like. This is my first time running into an error of this sort, and I'm not sure how to fix it. Can someone help me out?

    The error it throws is this:

    terminate called after throwing an instance of 'std::bad_alloc'
    what(): std::bad_alloc
    Aborted



    This is my merge function:

    Code:
    vector<int> merge(vector<int> array, int init, int mid, int size)
    {
    	int i;
    	int j;
    	int a1_size = mid - init + 1;
    	int a2_size = size - mid;
    	vector<int> left(a1_size);
    	vector<int> right(a2_size);
    
    
    	for(i = 0; i < a1_size; i++)
    	{
    		left[i] = array[init + i];
    	}
    
    
    	for(j = 0; j < a2_size; j++)
    	{
    		right[j] = array[mid + j];
    	}
    	left[a1_size + 1] = INT_MAX;
    	left[a2_size + 1] = INT_MAX;
    	i = 0;
    	j = 0;
    
    
    	for(int k = 0; k < array.size(); k++)
    	{
    		if(left[i] <= right[j])
    		{
    			array[k] = left[i];
    			i++;
    		}
    		else
    		{
    			array[k] = right[j];
    			j++;
    		}
    	}
    	left.clear();
    	right.clear();
    	return array;
    }
    And this is my merge sort:

    Code:
    vector<int> merge_sort(vector<int> array, int pos, int size)
    {
    	if(size == 1)
    	{
    		return array;
    	}
    	else
    	{
    		merge_sort(array, pos, size/2);
    		merge_sort(array, size/2+1, size/2);
    		merge(array, pos, size/2, size);
    		return array;
    	}
    }
    I think it is happening because of the recursive calls, because it works well up to 3 element arrays.

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    bad_alloc means memory allocation failed, e.g. not enough memory available.
    Looking at your code, that wouldn't be too surprising since you're making a lot of copies. Lines 1, 7, 8 in merge function and merge sort line 1 and possibly 12 are making copies of the array. If your array is big, you're going to run out of memory quickly and performance is going to hurt.

    First, you should take a look at references. That eliminates merge function line 1 and merge sort line 1. Next, you shouldn't make copies of the left and right arrays to sort. You should use indices, because each subsequent merge sort call only work with a subset of the original array. No need for copies. That eliminates merge function line 7 and 8. Finally, you should probably do an in-sort (i.e. modify the existing array you pass in). By doing this, you eliminate the return, hence fixing line 12 in merge sort.

    I'd say you should begin by fixing this first and then see how it performs.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    37,536
    > merge_sort(array, pos, size/2);
    > merge_sort(array, size/2+1, size/2);
    The range size/2+1 to size/2 does nothing.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,646
    Quote Originally Posted by Salem View Post
    The range size/2+1 to size/2 does nothing.
    Except that a2_size may be negative for vector<int> right(a2_size), and since vector sizes are of type size_t, unsigned, it's treated as a very large number.
    Last edited by rcgldr; 04-10-2016 at 11:41 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  3. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  4. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM
  5. help with merge sort
    By maloy in forum C Programming
    Replies: 4
    Last Post: 03-04-2002, 06:22 PM

Tags for this Thread