c++ - Memory leak in recursion -

i trying implement algorithm, using recursion. in recursion allocate memory using new , delete still memory leaks. tried understand i'm doing incorrectly couldn't figure out. can have please?

• i know can use vectors, understand did wrong , how fix it.

this code:

#include <iostream> #include <fstream> #include <math.h> #define _crtdbg_map_alloc #include <stdlib.h> #include <crtdbg.h> using namespace std;    int sortinv(int*,int); int sort_and_count_split_inv(int*,int,int,int); int sort_and_count(int *,int,int);  int main() {     _crtsetdbgflag ( _crtdbg_alloc_mem_df | _crtdbg_leak_check_df );     int siz = 9;     int arr[9] = {66,3,11,76,93,9,22,56,89};         int b = sort_and_count(arr,0,siz-1);     (int i=0; i<siz; i++)         arr[i] = arr[i];     return 0; }  int sort_and_count(int *a,int low,int high) {     int mid;     int n = 0;     if (low >= high)         return 0;     else         mid = (high+low)/2;         n+= sort_and_count(a,low, mid);         n+= sort_and_count(a, mid+1, high);         n+= sort_and_count_split_inv(a,low,mid,high);         return n; }  int sort_and_count_split_inv(int* a, int low, int mid, int high) {     int i,j,k;     i=low;     j=mid+1;     k=low;     int count = 0;     int* tmp = new int[high-low+1];     while (i<=mid && j<=high)     {         if (a[i]<a[j])         {             tmp[k] = a[i];             i++;         }         else         {             tmp[k] = a[j];             j++;             count += mid-i == 0? 1: mid+1-i;         }         k++;     }     while (i<=mid)         tmp[k++] = a[i++];     while (j<=high)         tmp[k++] = a[j++];     (i=low; i<=high; i++)         a[i] = tmp[i];     delete[] tmp;     _crtdumpmemoryleaks;     return count; } 

compiling code , running in valgrind produces first occurrence of memory leak:

==20797== invalid write of size 4 ==20797==    @ 0x400ba0: sort_and_count_split_inv(int*, int, int, int) (in /home/test/testcpp) ==20797==    0x4009d4: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x4009bc: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x4009a2: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x400921: main (in /home/test/testcpp) ==20797==  address 0x5a1d0ec 4 bytes after block of size 8 alloc'd ==20797==    @ 0x4c2b800: operator new[](unsigned long) (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so) ==20797==    0x400ae8: sort_and_count_split_inv(int*, int, int, int) (in /home/test/testcpp) ==20797==    0x4009d4: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x4009bc: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x4009a2: sort_and_count(int*, int, int) (in /home/test/testcpp) ==20797==    0x400921: main (in /home/test/testcpp) 

i nailed down line:

tmp[k] = a[i]; 

this means k reaches number larger length of allocated int[] array. since allocate length of high - low + 1 , k = low, surpass border case 2*low = high + 1.

i didn't go detail actual sorting algorithm , why you're feeding in wrong low (or high), memory leak comes from.