Click here to Skip to main content
15,885,767 members
Please Sign up or sign in to vote.
2.00/5 (1 vote)
See more:
I am currently working on sorting arrays and it was time for me to learn merge sort but while I was trying to code, it compiles but the Windows stops working. What may be the problem?
C++
int* mergeSort(int* arr){
	int size= sizeof(arr)/sizeof(arr[0]);
	if(size==1) return arr;
	
	int middle= size/2;
	int* rightArr= (int*)malloc(sizeof(int)*middle);
	int* leftArr= (int*)malloc(sizeof(int)*middle);
	
	for(int i=0; i<middle; i++){
		leftArr[i]= arr[i];
	} 
	
	for(int j=middle+1; j<size; j++){
		rightArr[j]= arr[j];
	}
	
	leftArr= mergeSort(leftArr);
	rightArr= mergeSort(rightArr);
	
	arr= merge(leftArr,rightArr);
	
	return arr;
}


What I have tried:

I've tried to change the code a few times but I still get the same error (windows stops working).
Posted
Updated 5-Apr-18 1:38am
v2
Comments
Mohibur Rashid 5-Apr-18 6:25am    
You tried to change your code and you are still getting the same error, what error?
Member 13763946 5-Apr-18 6:30am    
As I've mentioned, the code compiles correctly but windows stops running while executing the code.

C++
int* mergeSort(int* arr){
    int size= sizeof(arr)/sizeof(arr[0]);

The variable arr is declared as int* type, so its size is 4, and arr[0] is int type, so its size is also 4. So size will always equal 1.
 
Share this answer
 
Comments
CPallini 5-Apr-18 6:43am    
5.
Quote:
it compiles but the Windows stops working
That is not a good problem description. Windows is an operating system and it will usually not "stop working" when running a program that behaves unpredictable.

Do you mean your application (main window) is not responding anymore?
Then use a debugger to run your application step by step and inspect your variables.

You should have shown also the code of the merge() function and how you call the sort function.

However, there are at least two big mistakes and two others in your code

The first big one:
C++
int size= sizeof(arr)/sizeof(arr[0]);
arr is of type int* so that sizeof(arr) is 4 or 8 depending on the application type (32 or 64 bit). Dividing that by sizeof(int) results in size being always 1 or 2.

The solution is to add a function parameter specifying the number of items in the array:
int* mergeSort(int* arr, int items);

The second big one and others:
C++
int middle= size/2;
int* rightArr= (int*)malloc(sizeof(int)*middle);
// ...
for(int j=middle+1; j<size; j++){
    rightArr[j]= arr[j];
}
rightArr has middle (size/2) items but you are assigning values starting at middle+1. That is an out of bound array write access!
I would expect something like:
C++
for(int i = 0, j=middle; i<middle; i++, j++){
    rightArr[i]= arr[j];
}
Note also that I have changed the start index for arr from middle+1 to middle (other mistake).

The final mistake might be (you have to check if it applies) that you are not handling the case of odd sizes.
 
Share this answer
 
In C language, an array is simply its contain, the size is not stored anywhere with the array. You have to keep track of array size explicitly in a variable.

When you don't understand what is doing your code, the debugger allow you to execute the code line by line and to inspect variables.
There is a tool that allow you to see what your code is doing, its name is debugger. It is also a great learning tool because it show you reality and you can see which expectation match reality.
When you don't understand what your code is doing or why it does what it does, the answer is debugger.
Use the debugger to see what your code is doing. Just set a breakpoint and see your code performing, the debugger allow you to execute lines 1 by 1 and to inspect variables as it execute.

Debugger - Wikipedia, the free encyclopedia[^]

Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]
Basic Debugging with Visual Studio 2010 - YouTube[^]
The debugger is here to show you what your code is doing and your task is to compare with what it should do.
There is no magic in the debugger, it don't find bugs, it just help you to. When the code don't do what is expected, you are close to a bug.
 
Share this answer
 
If middle is not even than your code is total wrong. You absolutly miss some sorting in your code.

For a better understanding read the Rosettacode article about merge sort. You also find there some C code.

Last but not least: you need to free the with malloc allocated memory.

Good luck - you will need it. ;-)
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900