Merge Sort

[LmaverickD]

So I need to sort a 1000000 random numbers.
How do I declare a new array to hold the sorted value?
the program would run and would break when trying to sort it.

//Merge two sublist to one new arr
void merge(int arr[], int start, int mid, int end) {
	int i = start;
	int j = mid + 1;
	int k = start;
	/* create temp arrays */
	int arr2size = (end-start)+1;
	int* arr2 = new int [arr2size];

	/*cout << "Start time ";
	timing();*/
	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			arr2[k] = arr[i];
			i++;
		}
		else {
			arr2[k] = arr[j];
			j++;
		}
		k++;
	}
	if (i > mid) {
		while (j < end) {
			arr2[k] = arr[j];
			j++;
			k++;
		}
	}
	else {
		while (i <= mid) {
			arr2[k] = arr[i];
			i++;
			k++;
		}
	}
	/*cout << "End time ";
	timing(); */
}
//merge sort
void mergeSort(int arr[], int i, int j) {
	int mid;
	if (i < j) {
		int mid = (i + j) / 2;
		mergeSort(arr, i, mid);
		mergeSort(arr, mid + 1, j);
		merge(arr, i, mid, j);
	}
}

[jonnin]

Where do you delete arr2?
where do you USE arr2? I see assignments that fill it up, but it isnt returned or anything.

the way you create arr2 is correct. But you may be created a LOT of them and not deleting them, which might crash, or there could be some other bug. Its only a few MB for a million, so its not much in the modern world and you dynamically choose the size to fit, so they won't all be that large anyway.

[Manga]

#include <iostream>
#include <algorithm>

using namespace std;

//fill array
void copy(int source[], int target[], int size) {
    for(int i = 0; i < size; i++) {
      target[i] = source[i];
    }
}

//sort the array
void sort(int arr[], int size) {
    for(int i = 0; i < size; i++) {
        if(i + 1 < size && arr[i] > arr[i + 1]) {
            swap(arr[i], arr[i+1]);
            i = 0;
        }
    }
    
}

//print array
void print(int arr[], int size) {
  for(int i = 0; i < size; i++) {
   cout << arr[i] << " ";   
  }
  cout << endl;
}


int main()
{
  int a[] = { 2, 7, 5, 3, 2 };
  
  //get array size
  int length = sizeof(a) / sizeof(a[0]);
  
  //make new array 
  int* b = new int[length];
  
  copy(a, b, length);
  
  sort(b, length);
  
  print(b, length);
  
  delete b;
  return 0;
}

[LmaverickD]

@jonnin thank you. I think I see what you mean.
So should I call the arr2 in void merge?
Like this?

void mergeSort(int arr2[], int i, int j) {
	int mid;
	if (i < j) {
		int mid = (i + j) / 2;
		mergeSort(arr2, i, mid);
		mergeSort(arr2, mid + 1, j);
		merge(arr2, i, mid, j);
	}
}

How do I destroy the other array that I have created?
From what I understand from my lecture, at the end of the recursion there would be 2 sublist that have been sorted and that sublist will be put to the new list witch is the arr2 that was created?

[LmaverickD]

@Manga would you be able to explain the logic behind your sort?
It seems very different from Merge Sort that I have seen so far.
It seems like you don't split the list into two?

[dhayden]

After you merge into the arr2 array, you have to copy arr2 back into arr.

When using C++, it's always a good idea to express ranges as [start, end). In other words, start is inside the range and end is not. This is the way the standard library does it it.

Here is your code copying arr2, with the ranges modified as I mentioned, and with a main program to test it.

#include <iostream>
#include <vector>

using std::vector;
using std::cin;
using std::cout;


//Merge two sorted sublist in arr.
// List 1 is from [start, mid)
// List 2 is from [mid, end)
void
merge(int arr[], int start, int mid, int end)
{
    int i = start;		// source idx in list 1
    int j = mid;		// source idx in list 2
    int k = 0;			// destination in ar2
    /* create temp arrays */
    int arr2size = end - start;
    int *arr2 = new int[arr2size];

    /*cout << "Start time ";
       timing(); */
    while (i < mid && j < end) {
	if (arr[i] <= arr[j]) {
	    arr2[k++] = arr[i++];
	} else {
	    arr2[k++] = arr[j++];
	}
    }

    // The i side or the j side still have values left.
    // Copy them in. Rather than trying to figure out which
    // one must be copied, code it to copy both. To me, it's
    // clearer that way.  Only one of these while loops will
    // actually execute.
    while (j < end) {
	arr2[k++] = arr[j++];
    }
    while (i < mid) {
	arr2[k++] = arr[i++];
    }
    
    // Now copy the values from arr2 back into arr
    for (k=0; k<arr2size; ++k) {
	arr[start+k] = arr2[k];
    }

    delete[] arr2;
}

//merge sort values in arr in the interval [i,j)
void
mergeSort(int arr[], int i, int j)
{
    if (i+1 < j) {		// if there are 2 or more values
	int mid = (i + j) / 2;
	mergeSort(arr, i, mid);
	mergeSort(arr, mid, j);
	merge(arr, i, mid, j);
    }
}

int main()
{
    vector<int> vec;
    int val;
    while (cin >> val) {
	vec.push_back(val);
    }

    mergeSort(&vec[0], 0, vec.size());

    for (auto v: vec) {
	cout << v << ' ';
    }
    cout << '\n';
}

[Manga]

Maybe I don't fully understand what you are trying to do. I thought you wanted a new array that is a sorted version of the first. That is all I did.

[LmaverickD]

@Manga I see what you mean! Thank you!

dhayden thank you for taking your time to explain it

I tried deleting arr2 as you shown and it gave me a HEAP CORRUPTION DETECTED ERROR (CTR detected that the application wrote to memory after end of heap buffer).
It shouldn't do that theoretically right as everything have been copy or moved to the old arr from all the recursion that happened in arr2?

It gave me that no matter if I use vector as you shown or in my case before I use for loop to print my arr.

void printArray(int* arr, int size) {
	int min, max;
	cout << "Enter a min:";
	cin >> min;
	cout << "Enter a max:";
	cin >> max;

	for (int i = min; i < max; i++) {
		cout << arr[i] << " ";
		cout << endl;
	}
}

I know that using a vector is more beneficial while dealing with a growing number.
How do I impalmented vector to my current for loop here?

[dhayden]

I tried deleting arr2 as you shown and it gave me a HEAP CORRUPTION

From your original code:

void merge(int arr[], int start, int mid, int end) {
	int i = start;
	int j = mid + 1;
	int k = start;
	/* create temp arrays */
	int arr2size = (end-start)+1;
	int* arr2 = new int [arr2size];

	/*cout << "Start time ";
	timing();*/
	while (i <= mid && j <= end) {
		if (arr[i] <= arr[j]) {
			arr2[k] = arr[i];
			i++;

Suppose you call merge(arr, 5, 7, 10):
Line 2: i=5
Line 3: j=8
Line 4: k=5
Line 6: arr2size = 6;
Line 7: arr2 = new int[6];
...
Line 13 (first time): arr2[5] = arr[i];
Line 13 (second time): arr2[6] = arr[i] // !! accessing arr2 out of bounds

[seeplus]

I tried deleting arr2 as you shown and it gave me a HEAP CORRUPTION

For cases when there is a run-time issue, use the debugger to trace through the code, see the order of execution and monitor the values of variables. Then you know where execution isn't as expected and where results deviate.

[LmaverickD]

Ok So I think I finally understand the problem. So I need arr2 to be the same size of the original arr to be able to handle the numbers.
As my previous code was saying that I have arr2 half+1 size that is why I got a HEAP CORRUPTION.

I tried using

/* create temp arrays */
	int arr2size = (end+start)+1;
	int* arr2 = new int [arr2size];

From my understanding that should create enough space for the arr2 ass let say start is 0 and end is 10. So the arr2size should be 11 which should have enough space for the numbers.
But it still giving me an error.

I couldn't think of anything else.

[LmaverickD]

update I use
int arr2size = start + (end - start)/2;
it gave me the result of unsorted number

[ne555]

> Ok So I think I finally understand the problem.
> So I need arr2 to be the same size of the original arr to be able to handle the numbers.
no
the problem is that you do k=start when you should be doing k=0

> update I use
I've got lost in your patches, post the full updated code.
with a proper main() to test your function


also, ¿was dhayden's not good enough?