Last active
August 29, 2015 14:25
-
-
Save stanroze/26acdd413ff1e22cee17 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
static void msort(int[] arr) | |
{ | |
if (arr.Length == 1) | |
return; | |
//get a half point | |
int mid = arr.Length/2; | |
int[] left = new int[mid]; | |
int[] right = new int[arr.Length - mid]; //reason for length - mid is due to halfpoint of an odd length array | |
//fill up left - to the half point from original | |
for (int i = 0; i < mid; i++) | |
{ | |
left[i] = arr[i]; | |
} | |
//fill up right - need j because right arr starts at 0, start at mid for the parent array | |
for (int i = mid, j = 0; i < arr.Length; i++, j++) | |
{ | |
right[j] = arr[i]; | |
} | |
//you have 2 arrays, so sort both of them | |
//you can of course use merge to return a new array | |
//but its better to sort the array in space | |
msort(left); | |
msort(right); | |
//each sort has to merge the 2 halves, this is techincally where the "sort" happens | |
//the 2 halves starting with the most smallest arrays of 1 item | |
//this will sort those 2 arrays items and put them into the parent array | |
merge(left, right, arr ); | |
} | |
private static void merge(int[] arrA, int[] arrB, int[] aux) | |
{ | |
//you can of course return a "new" array here, but why allocate more | |
int aindex = 0; | |
int bindex = 0; | |
int auxindex = 0; | |
//we need to compare each element in both arrays and only pick the smallest one | |
//once the smallest one is picked, increment in indexer in the array it was picked from | |
//and leave the other indexer untouched. | |
//always increment the auxilary index | |
while (aindex < arrA.Length && bindex < arrB.Length) | |
{ | |
if (arrA[aindex] < arrB[bindex]) | |
{ | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
} | |
else if (arrB[bindex] < arrA[aindex]) | |
{ | |
aux[auxindex] = arrB[bindex]; | |
bindex++; | |
} | |
else | |
{ | |
//numbers are identical, makes no difference, just pick from one array and increment it | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
} | |
auxindex++; | |
} | |
//in the even that all the smallest numbers were in one of the arrays instead of other | |
//we need to fill up the parent array with the items from the other side, so just | |
//fill up until we cant anymore | |
//first do from A Array | |
while (aindex < arrA.Length) | |
{ | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
auxindex++; | |
} | |
//then do the same from B array | |
while (bindex < arrB.Length) | |
{ | |
aux[auxindex] = arrB[bindex]; | |
bindex++; | |
auxindex++; | |
} | |
//done :D | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment