|
Merge sort with nlogn speed of processing is one of the quickest methods for sorting. This method uses
tree and nodes. Here is a brief explanation of merge sort algorithm:
1. Getting the array and splitting it into two equal sub array (if length of array is an odd number, length of
one sub array will be more than the other)
2. Return to step 1 when any of sub arrays have a length more than or equal to 2
3. Merge two sub arrays
Merge is a way for combining two sorted arrays that the result array is sorted too. Note that above
algorithm is recursive. There is an algorithm for merge sort that is not recursive, but it's too twisted. Soon I'll
write an article for it. Recursion stops when it reaches an array with length 0 or 1 (for both sub arrays), because
it's a sorted array. After that two sub arrays will be merged and our array will be sorted. Below you can see the code
of MergeSort recursive function that can sort an array of strings:
private void MergeSort(string[] a)
{
string[] a1 = SubArray(a, 0, a.Length / 2 - 1);
string[] a2 = SubArray(a, a.Length / 2, a.Length - 1);
if (a1.Length > 1) MergeSort(a1);
if (a2.Length > 1) MergeSort(a2);
Merge(a1, a2, a);
}
SubArray function receives an array returns a sub array of it depending on
the start index (parameter two named start) and the end index (parameter three named end). This is the code:
private string[] SubArray(string[] array, int start, int end)
{
string[] sub = new string[end - start +
1];
for (int i = start; i <= end && i
< array.Length; i++)
{
sub[i - start] = array[i];
}
return sub;
}
Merge function merges two arrays given in parameters one and two into array
on parameter three. It acts as I told above. As you know, main sorting part of merge sort is this function:
private void Merge(string[] a1, string[] a2, string[] a)
{
int i = 0, j = 0, h = 0;
while (i < a1.Length || j < a2.Length)
{
if (i == a1.Length) a[h++] = a2[j++];
else if (j == a2.Length) a[h++] = a1[i++];
else
if (a1[i].CompareTo(a2[j]) < 0)
{
a[h++] = a1[i++];
}
else if (a1[i].CompareTo(a2[j]) > 0)
{
a[h++] = a2[j++];
}
else
{
a[h++] = a1[i++];
a[h++] = a2[j++];
}
}
}
|
IP: 38.103.63.59 |
Country: United States
|
Browser: Unknown |
OS: Unknown |
|
| 
Operator Overloading
MergeSort (.Net 1.1) - 21.63 KB
