Java: Merge sort iterative implementation

MergeSort.java

package com.sample.app.algos;

import java.util.Comparator;
import java.util.List;
import java.util.ListIterator;

public class MergeSort {
	private MergeSort() {
	
	}

	public static <T> void sort(List<T> list, Comparator<? super T> comparator) {

		if (list == null || list.size() < 2) {
			return;
		}

		if (comparator == null) {
			throw new IllegalArgumentException("Comparator must be supplied");
		}

		Object[] arr = list.toArray();
		sortIteratively(arr, (Comparator) comparator);

		ListIterator<T> listIterator = list.listIterator();
		for (Object ele : arr) {
			listIterator.next();
			listIterator.set((T) ele);
		}
	}

	private static <T> void sortIteratively(T[] array, Comparator<? super T> comparator) {

		T[] aux = array.clone();

		for (int blockSize = 1; blockSize < array.length; blockSize = (blockSize << 1)) {
			for (int start = 0; start < array.length; start += (blockSize << 1)) {
				merge(array, aux, start, start + blockSize, start + (blockSize << 1), comparator);
			}
		}
	}

	private static <T> void merge(T[] arr, T[] aux, int from, int mid, int to, Comparator<? super T> cmp) {
		if (mid >= arr.length) {
			return;
		}
		if (to > arr.length) {
			to = arr.length;
		}
		int i = from;
		int j = mid;
		for (int k = from; k < to; k++) {
			if (i == mid) {
				aux[k] = arr[j++];
			} else if (j == to) {
				aux[k] = arr[i++];
			} else if (cmp.compare(arr[j], arr[i]) < 0) {
				aux[k] = arr[j++];
			} else {
				aux[k] = arr[i++];
			}
		}
		System.arraycopy(aux, from, arr, from, to - from);
	}
}

 

MergeSortDemo.java

package com.sample.app.algos;

import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class MergeSortDemo {

	public static void main(String[] args) {
		List<Integer> list = Arrays.asList(5, 46, 25, 13, 12);

		MergeSort.sort(list, new Comparator<Integer>() {

			@Override
			public int compare(Integer data1, Integer data2) {
				return data1.compareTo(data2);
			}
		});

		for (Integer data : list) {
			System.out.println(data);
		}
	}

}

 

Output

5
12
13
25
46

 

You may like

Design Patterns

Interview Questions

Programming Questions

Reverse the elements of stack

Java program to find a cycle in undirected graph

Check whether number is even or odd using bitwise operator