Merge sort Java arraylist
In this post, you will learn how to write the merge sort program using the Java programming language.
Merge sort an efficient, general-purpose, and comparison-based sorting algorithm. It is one of the most important sorting algorithms based on the divide and conquer technique. Merge sort is very popular for its efficiency in sorting the data in a small amount of time with worst-case time complexity Ο(n log n). Merge sort first divides the element lists into their two halves. The sub lists are divided again and again into halves until we get only one element from each. Then we combine the pairs of one element lists into two element lists, sorting them in the process and, at last, putting them all together.
These are the processes that merge sort follows-
- Divide- It partitions the n elements of the array into two sub arrays.
- Conquer- It sorts the two sub arrays using merge sort.
- Combine- It merges the two sorted sequences to produce the sorted array.
Complexity of Merge Sort
Suppose n is the number of elements in an array.
Best Time Complexity - O(n)
Worst Time Complexity - O(n2)
Average Time Complexity - O(n2)
Advantages Of Merge Sort
- Merge sort is a stable sorting algorithm.
- Merge sort is well suited for large data set.
- It has a consistent running time and carries out different bits at similar times in a stage.
Disadvantages Of Merge Sort
- Slower comparative to the other sort algorithms for smaller tasks.
- At least twice the memory requirements than other sorts.
Merge Sort Program in Java
import java.util.ArrayList;
public class SortArrayList {
private final ArrayList arrayToSort;
public SortArrayList(ArrayList arrayToSort) {
this.arrayToSort = arrayToSort;
}
public ArrayList getArrayAfterSorting() {
return arrayToSort;
}
public void divideElements(int start, int end) {
if (start < end && (end - start) >= 1) {
int midElement = (end + start) / 2;
divideElements(start, midElement);
divideElements(midElement + 1, end);
mergeElements(start, midElement, end);
}
}
public void mergeElements(int start, int mid, int end) {
ArrayList tempArr = new ArrayList<>();
int getLeftIndex = start;
int getRightIndex = mid + 1;
while (getLeftIndex <= mid && getRightIndex <= end) {
if (arrayToSort.get(getLeftIndex) <= arrayToSort.get(getRightIndex)) {
tempArr.add(arrayToSort.get(getLeftIndex));
getLeftIndex++;
} else {
tempArr.add(arrayToSort.get(getRightIndex));
getRightIndex++;
}
}
while (getLeftIndex <= mid) {
tempArr.add(arrayToSort.get(getLeftIndex));
getLeftIndex++;
}
while (getRightIndex <= end) {
tempArr.add(arrayToSort.get(getRightIndex));
getRightIndex++;
}
for (int i = 0; i < tempArr.size(); start++) {
arrayToSort.set(start, tempArr.get(i++));
}
}
public static void main(String[] args) {
ArrayList arrList = new ArrayList<>();
arrList.add(24);
arrList.add(11);
arrList.add(8);
arrList.add(6);
arrList.add(53);
SortArrayList sortObj = new SortArrayList(arrList);
System.out.println("Array Before Merge Sort: ");
for (Integer integer : sortObj.getArrayAfterSorting()) {
System.out.println(integer);
}
System.out.println();
sortObj.divideElements(0, arrList.size() - 1);
System.out.println("Array After Merge Sort: ");
for (Integer integer : sortObj.getArrayAfterSorting()) {
System.out.println(integer);
}
}
}
Output of the above code:
Array Before Merge Sort: 24
11
8
6
53
Array After Merge Sort:
6
8
11
24
53
Related Articles
Java string split multiple delimitersEnum with values in Java
Convert array to list in Java
Java random number between 1 and 100
Calculating percentage in Java
Multiplication table program in Java
Java dialogue box
Fibonacci series using recursion in Java
Java sum of array
Circular prime in Java
Vowel and Consonant program in Java
Convert binary to decimal in Java
Convert decimal to binary in Java
Convert decimal to octal in Java
Convert decimal to hexadecimal in Java
Simple interest program in Java
Check whether the given number is even or odd in java
Print prime numbers from 1 to 100 in Java
Java prime number program
Java program to convert celsius to fahrenheit
Java program to check leap year
Java program to find factorial of a number