Sorting
and Searching
Merge Sort
The merge sort algorythm is much more efficient
than the selection sort. It specializes in meging two sorted
arrays. But what if those two arrays are not sorted? It
merge sorts them as well, by cutting them in to two pre-sorted arrays,
and merging the sorted arrays. What if those two halves of the
original half arrays are not sorted? It continues the process -
that's right - recursively.The pseudocode for a merge sort recursive method is this:
// method signature
sort {
If the length of the array A is 1
or less, then it is automatically sorted. Return.
Create an array, called first, that is half of the length of the array A.
Create an array, called second, that is the lenght of array A minus the lenght of the array first.
Copy all elements from array A to array first and second.
Create a new object of the class that contains this method. Pass it the first array.
Create a new object of the class that contains this method. Pass it the second array.
Call this sort method recursively on first.
Call this sort method recursively on second.
Call a merge method to merge the now-sorted first and second.
}Create an array, called first, that is half of the length of the array A.
Create an array, called second, that is the lenght of array A minus the lenght of the array first.
Copy all elements from array A to array first and second.
Create a new object of the class that contains this method. Pass it the first array.
Create a new object of the class that contains this method. Pass it the second array.
Call this sort method recursively on first.
Call this sort method recursively on second.
Call a merge method to merge the now-sorted first and second.
merge (array A, array B) {
Create a counter for array A and
Array B.
loop while the counter for A is less than the length of A, AND the counter for B is less than the length of B {
loop while the counter for A is less than the length of A, AND the counter for B is less than the length of B {
Compare the value of array B at
counter B with array A at counter A. Add the lowest one to a new
'holder' array. Increment the counter of the array that
originally had that lowest value.
}
Copy any remaining entries.
}Copy any remaining entries.
The merge sort has n(log(n)) performance, compared to the selection sort's n2 performance - whatever that means.
JDBC Drivers