Basically I needed to sort a list of raycasthit base on distance, and I was gonna write my own merge sort. I tried to test the merge sort with a list of ints, and the moment i hit play, unity crashed. Heres the code:
void sort (List<int> tempH)
{
if (tempH.Count > 1) {
int mid = tempH.Count / 2;
List<int> left = new List<int> ();
popullate (0, mid-1, left, tempH);
sort (left);
List<int> right = new List<int> ();
popullate (mid, tempH.Count - 1, right, tempH);
sort (right);
tempH = merge (left, right);
} else {
return;
}
}
List<int> merge (List<int> left, List<int> right)
{
List<int> temp = null;
int i = 0;
int j = 0;
while (i < left.Count || j < right.Count) {
if (i < left.Count && j < right.Count) {
if (left *< right [j]) {*
It looks like your problem is at line 27. You set your temp list to null, but then never initialize it before trying to add elements to it on line 35. Change it to List<int> temp = new List<int>(); and that should solve your problem.
You have an infinite recursion due to a wrong limit in line 58:
for (int i = leftIndex; i <= rightIndex; i++) {
In case there are two elements in your list mid will be 1 ( == 2 / 2). For your left list your leftIndex is 0 and rightIndex is 1. Therefore you copy both elements to the new list and doing that until you get a stackoverflow.
LazyElephant is right about your temp list, however that would just raise a null reference exception and terminate the execution.
I haven’t checked if the rest of your implementation is “correct”. However what i can say is that it’s going to be very inefficient. You create a lot of garbage
The first implementation on the wiki will be much faster and doesn’t create as much garbage. It only requires a single temp array which has the same size as the source array.
Apart from creating way too much temp lists, each of those temp lists will have to resize when you add elements. So the first lists which contains many elements will resize a couple of times. Each resize will create additional garbage and the temp list might even be larger than necessary.