Click here to Skip to main content
14,304,331 members
Rate this:
Please Sign up or sign in to 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?
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.
Rate this:
Please Sign up or sign in to vote.

Solution 1

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.
   
Comments
CPallini 5-Apr-18 6:43am
   
5.
Rate this:
Please Sign up or sign in to vote.

Solution 2

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:
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:
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:
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.
   
Rate this:
Please Sign up or sign in to vote.

Solution 3

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.
   
Rate this:
Please Sign up or sign in to vote.

Solution 4

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. ;-)
   

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




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100