0

Hello, I am working on a merge sort but I keep getting the following error : ds07(6443) malloc: *** error for object 0x100100098: incorrect checksum for freed object - object was probably modified after being freed. I don't see what my error is with the creation and deletion of my dynamic memory. Any help would be appreciated

void Array::mergeSort (void) 
    {
        mergeSort (0, size-1); // call to private : merge
    }
    
    void Array::mergeSort (int first, int last)
    {
            if (last > first)// more than one in subarray
            {
                int mid = (first + last) / 2;
                mergeSort (first, mid);
                mergeSort (mid+1, last);
                merge (first, last);
            } 
    }
    
    void Array::merge (int first, int last)
    {
        int* merged = new int [last-first+1];
        int mid = (first + last) / 2;
        int secList = mid + 1; // beginning of second list
        int firstList = first; //beginning of first list
        int j = first; // used for array index assignment

       while ( (firstList <= mid) && (secList <= last) )// both lists #1 & #2 are not exhausted
        {
            if (data[firstList] < data[secList])// data in list #1 < data in list #2
            {
                merged[j] = data[firstList];// <- data in list #1
                firstList++;
            }   
            else
            {
                merged[j] = data[secList]; // <- data in list #2
                secList++;
            }
            j++;
        } // end while
        
        if (firstList > mid)
        {
            for (int q = secList; q <= last; q++){
                merged[j] = data[q];
                j++;
            }
        }
        else
        {
            for (int r = firstList; r <= mid; r++)
            {
                merged[j] = data[r];
                j++;
            }
        }
      
        for (int i = first; i <= last; i++)
        {
            data[i] = merged[i];// overwrite original positions with "merged"
        }
       delete [ ] merged; //commented out due to segmentation fault
       merged = NULL;
    }
2
Contributors
1
Reply
3
Views
7 Years
Discussion Span
Last Post by mitrmkar
1

Here's a version with some assert() added. Run it in the debugger and you'll probably be spotting errors quite quickly.

#include <cassert>

void Array::merge (int first, int last)
{
  const int arr_size = last-first+1;

  int* merged = new int[arr_size];
  int mid = (first + last) / 2;
  int secList = mid + 1; // beginning of second list
  int firstList = first; //beginning of first list
  int j = first; // used for array index assignment

  while ( (firstList <= mid) && (secList <= last) )// both lists #1 & #2 are not exhausted
  {
      if (data[firstList] < data[secList])// data in list #1 < data in list #2
      {
          // check j ...
          assert(j < arr_size);
          merged[j] = data[firstList];// <- data in list #1
          firstList++;
      }   
      else
      {
          // check j ...
          assert(j < arr_size);
          merged[j] = data[secList]; // <- data in list #2
          secList++;
      }
      j++;
  } // end while
    
  if (firstList > mid)
  {
      for (int q = secList; q <= last; q++){
          // check j ...
          assert(j < arr_size);
          merged[j] = data[q];
          j++;
      }
  }
  else
  {
      for (int r = firstList; r <= mid; r++)
      {
        // check j ...
        assert(j < arr_size);
        merged[j] = data[r];
        j++;
      }
  }

  for (int i = first; i <= last; i++)
  {
      data[i] = merged[i];// overwrite original positions with "merged"
  }

   delete [ ] merged; //commented out due to segmentation fault
   merged = NULL;
}

I'd suggest you to check all your code for out-of-bound writes.

This question has already been answered. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.