java left logo
java middle logo
java right logo
 

Home arrow Java SE Tips
 
 
Main Menu
Home
Java Tutorials
Book Reviews
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Java Network
Java Forums
Java Blog




Most Visited Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews
Top Rated Tips
Java SE Tips
Java ME Tips
Java EE Tips
Other API Tips
Java Applications
Java Libraries
Java Games
Book Reviews


Statistics
Registered Users: 4092
Java SE Tips: 614
Java ME Tips: 202
Java EE Tips: 183
Other API Tips: 779
Java Applications: 298
Java Libraries: 209
Java Games: 16
Book Reviews:
 
 
 
Merge Sort Implementation in Java E-mail
User Rating: / 312
PoorBest 

In computer science, merge sort or mergesort is a sorting algorithm for rearranging lists (or any other data structure that can only be accessed sequentially, e.g. file streams) into a specified order. It is a particularly good example of the divide and conquer algorithmic paradigm. It is a comparison sort.

Conceptually, merge sort works as follows:

  1. Divide the unsorted list into two sublists of about half the size
  2. Sort each of the two sublists
  3. Merge the two sorted sublists back into one sorted list.

The algorithm was invented by John von Neumann in 1945.

The following code shows how to implement merge sort in Java.

    /**
     * Mergesort algorithm.
     @param a an array of Comparable items.
     */
    public static void mergeSortComparable [ ] ) {
        Comparable [ ] tmpArray = new Comparablea.length ];
        mergeSorta, tmpArray, 0, a.length - );
    }
    
    /**
     * Internal method that makes recursive calls.
     @param a an array of Comparable items.
     @param tmpArray an array to place the merged result.
     @param left the left-most index of the subarray.
     @param right the right-most index of the subarray.
     */
    private static void mergeSortComparable [ ] a, Comparable [ ] tmpArray,
            int left, int right ) {
        ifleft < right ) {
            int center = left + right 2;
            mergeSorta, tmpArray, left, center );
            mergeSorta, tmpArray, center + 1, right );
            mergea, tmpArray, left, center + 1, right );
        }
    }
    
    /**
     * Internal method that merges two sorted halves of a subarray.
     @param a an array of Comparable items.
     @param tmpArray an array to place the merged result.
     @param leftPos the left-most index of the subarray.
     @param rightPos the index of the start of the second half.
     @param rightEnd the right-most index of the subarray.
     */
    private static void mergeComparable [ ] a, Comparable [ ] tmpArray,
            int leftPos, int rightPos, int rightEnd ) {
        int leftEnd = rightPos - 1;
        int tmpPos = leftPos;
        int numElements = rightEnd - leftPos + 1;
        
        // Main loop
        whileleftPos <= leftEnd && rightPos <= rightEnd )
            ifaleftPos ].compareToarightPos ] ) <= )
                tmpArraytmpPos++ = aleftPos++ ];
            else
                tmpArraytmpPos++ = arightPos++ ];
        
        whileleftPos <= leftEnd )    // Copy rest of first half
            tmpArraytmpPos++ = aleftPos++ ];
        
        whilerightPos <= rightEnd )  // Copy rest of right half
            tmpArraytmpPos++ = arightPos++ ];
        
        // Copy tmpArray back
        forint i = 0; i < numElements; i++, rightEnd-- )
            arightEnd = tmpArrayrightEnd ];
    }

 Related Tips

 
< Prev   Next >

Page 1 of 0 ( 0 comments )

You can share your information about this topic using the form below!

Please do not post your questions with this form! Thanks.


Name (required)


E-Mail (required)

Your email will not be displayed on the site - only to our administrator
Homepage(optional)



Comment Enable HTML code : Yes No



 
       
         
     
 
 
 
   
 
 
java bottom left
java bottom middle
java bottom right
RSS 0.91 FeedRSS 1.0 FeedRSS 2.0 FeedATOM FeedOPML Feed

Home - About Us - Privacy Policy
Copyright 2005 - 2008 www.java-tips.org
Java is a trademark of Sun Microsystems, Inc.