Sort Arrays – Merge Sort
Posted by admin - Apr 2, 2008 Arrays, Articles, Dani Vainstein, QTips 0 0 Views : 412 Receive Updates For This Category
Article Tools
- Print this page
- Add Comment
- Send to Friend
- Last Updated on :
Jul 16, 2011
In computer science, merge sort or mergesort is an O(n log n) comparison-based sorting algorithm. It is stable, meaning that it preserves the input order of equal elements in the sorted output. It is an example of the divide and conquer algorithmic paradigm. It was invented by John von Neumann in 1945.
The merge sort splits the list to be sorted into two equal halves, and places them in separate arrays. Each array is recursively sorted, and then merged back together to form the final sorted list.
Like most recursive sorts, the merge sort has an algorithmic complexity of O(n log n).
Elementary implementations of the merge sort make use of three arrays – one for each half of the data set and one to store the sorted list in. The below algorithm merges the arrays in-place, so only two arrays are required. There are non-recursive versions of the merge sort, but they don’t yield any significant performance enhancement over the recursive algorithm on most machines.
Public Sub MergeSort( ByRef arr(), ByRef temp(), ByVal nFirstIndex, ByVal nLastIndex )
Dim nMiddle
If nLastIndex > nFirstIndex Then
' ** Recursively sort the two halves of the list.
nMiddle = ( nFirstIndex + nLastIndex ) \ 2
Call MergeSort( arr, temp, nFirstIndex, nMiddle )
Call MergeSort( arr, temp, nMiddle + 1, nLastIndex )
' ** Merge the results.
Call Merge( arr, temp, nFirstIndex, nMiddle + 1, nLastIndex )
End If
End Sub
Private Sub Merge( ByRef arr(), ByRef temp(), ByVal nLeft, ByVal nMiddle, ByVal nRight )
Dim i, left_end, num_elements, tmp_pos
left_end = nMiddle - 1
tmp_pos = nLeft
num_elements = nRight - nLeft + 1
Do While( nLeft <= left_end ) And ( nMiddle <= nRight )
If arr( nLeft ) <= arr ( nMiddle ) Then
temp( tmp_pos ) = arr( nLeft )
tmp_pos = tmp_pos + 1
nLeft = nLeft + 1
Else
temp( tmp_pos ) = arr( nMiddle )
tmp_pos = tmp_pos + 1
nMiddle = nMiddle + 1
End If
Loop
Do While nLeft <= left_end
temp( tmp_pos ) = arr( nLeft )
nLeft = nLeft + 1
tmp_pos = tmp_pos + 1
Loop
Do While nMiddle <= nRight
temp( tmp_pos ) = arr( nMiddle )
nMiddle = nMiddle + 1
tmp_pos = tmp_pos + 1
Loop
For i = 0 To num_elements - 1
arr( nRight ) = temp( nRight )
nRight = nRight - 1
Next
End Sub
