Sorting algorithms are used everyday to sort all types of information in computer programs so I decided to share a O(Nlog2N) sorting algorithm called Merge Sort with you today. This is written in Java Programming. I shared a post last year on Quick Sort algorithm and I just decided to do all of the Big-O (Nlog2N) sorting algorithms. Of course Java has many built in data structures and uses the best sorting algorithms already, but if you are learning about data structures and algorithms you might find this post handy.
First I will post the Circle class just like in the Quicksort example that can be found here by the way QuickSort sorting algorithm in java with Generics that implement Comparable
Circle.java
/*** author: copypasteearth* date: 7/17/2019*/public class Circle implements Comparable<Circle> {public int xValue;public int yValue;public int radius;
@Override
public int compareTo(Circle o) {
return (this.radius - o.radius);
}
@Override
public String toString() {
return "x: " + xValue + " ---y: " + yValue + " ---radius: " + radius;
}
}
Secondly you are going to need the MergeSort class which also has the main method inside it so it can run the program. The class has static methods called merge and mergeSort that do all of the work. They basically keep splitting and sorting the array untill everything is sorted and then merges it all back together.
MergeSort.java
import java.util.Arrays;import java.util.Random;
/**
* author: copypasteearth
* date: 7/17/2019
*/
public class MergeSort<T extends Comparable<T>> {
public static <T extends Comparable<T>> void merge(int leftFirst, int leftLast, int rightFirst, int rightLast, T[] array){
T[] tempArray = Arrays.copyOf(array,array.length);
int index = leftFirst;
int saveFirst = leftFirst;
while((leftFirst <= leftLast) && (rightFirst <= rightLast)){
if(array[leftFirst].compareTo(array[rightFirst]) < 0){
tempArray[index] = array[leftFirst];
leftFirst++;
}else{
tempArray[index] = array[rightFirst];
rightFirst++;
}
index++;
}
while(leftFirst <= leftLast){
tempArray[index] = array[leftFirst];
leftFirst++;
index++;
}
while(rightFirst <= rightLast){
tempArray[index] = array[rightFirst];
rightFirst++;
index++;
}
for(index = saveFirst; index <= rightLast;index++){
array[index] = tempArray[index];
}
}
public static <T extends Comparable<T>> void mergeSort(int first, int last,T[] array){
if(first < last){
int middle = (first + last) / 2;
mergeSort(first,middle,array);
mergeSort(middle+1,last,array);
merge(first,middle,middle+1,last,array);
}
}
public static void main(String[] args){
Circle[] circlearray = new Circle[20];
Random rand = new Random();
for (int index = 0; index < 20; index++)
{
circlearray[index] = new Circle();
circlearray[index].xValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].yValue = Math.abs(rand.nextInt()) % 100;
circlearray[index].radius = Math.abs(rand.nextInt()) % 100;
}
System.out.println("Circle Array Unsorted....");
for(int i = 0;i < 20;i++){
System.out.println(circlearray[i]);
}
MergeSort<Circle> mscircle = new MergeSort<Circle>();
mscircle.mergeSort( 0, circlearray.length-1,circlearray);
System.out.println("Circle Array Sorted");
for(Circle i: circlearray) {
System.out.println(i);
}
}
}
And that pretty much sums it up for MergeSort. Another one of your should be favorited sorting algorithms that run at a whopping O(Nlog2N) complexity. Thanks for your time and i hope you liked this article and got some use out of it. I am leaving the Link to this and QuickSort on github here it is https://github.com/copypasteearth/Sorting
NSPENCM 85W Mac Book Pro Charger, Replacement AC 85w 2T-Tip Connector Power Adapter,Laptop Charger Compatible with MacBook pro & Mac Book Pro 13 inch-15 inch Retina After Mid 2012
$19.99 (as of January 22, 2025 08:46 GMT -05:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
Amazon Fire HD 10 tablet (newest model) built for relaxation, 10.1" vibrant Full HD screen, octa-core processor, 3 GB RAM, 32 GB, Black
$94.99 (as of January 22, 2025 08:46 GMT -05:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
Mac Book Pro Charger - 96W USB C Charger Fast Charger for USB C Port MacBook pro & MacBook Air, ipad Pro, Samsung Galaxy and All USB C Device, 6.6 ft USB C to USB C Cable Included
$19.99 (as of January 22, 2025 08:46 GMT -05:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
HP 14 Laptop, Intel Celeron N4020, 4 GB RAM, 64 GB Storage, 14-inch Micro-edge HD Display, Windows 11 Home, Thin & Portable, 4K Graphics, One Year of Microsoft 365 (14-dq0040nr, Snowflake White)
$174.95 (as of January 22, 2025 08:46 GMT -05:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
USB C Docking Station Dual HDMI Monitor,USB C to Dual HDMI Adapter with 2 HDMI Ports,PD Charging,SD/TF,USB A&C 3.0 Ports,USB C Hub HDMI for Dell XPS/HP/Lenovo/Surface/Yoga etc
$32.63 (as of January 22, 2025 08:46 GMT -05:00 - More infoProduct prices and availability are accurate as of the date/time indicated and are subject to change. Any price and availability information displayed on [relevant Amazon Site(s), as applicable] at the time of purchase will apply to the purchase of this product.)
Author: John Rowan
I am a Senior Android Engineer and I love everything to do with computers. My specialty is Android programming but I actually love to code in any language specifically learning new things.
Share this:
