Merge Sort
void merge(int arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
int[] L = new int[n1];
int[] R = new int[n2];
/* Copy data to temp arrays */
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
// MISSING CODE #1
arr[k] = L[i];
i++;
}
else {
// MISSING CODE #2
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public class Hack {
void merge(String arr[], int l, int m, int r)
{
// Find the sizes of two subarrays to be merged
int n1 = m - l + 1;
int n2 = r - m;
/* Create temp arrays */
String[] L = new String[n1];
String[] R = new String[n2];
/* Copy data to temp arrays */
for (int i = 0; i < n1; ++i)
L[i] = arr[l + i];
for (int j = 0; j < n2; ++j)
R[j] = arr[m + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged subarray array
int k = l;
while (i < n1 && j < n2) {
if (L[i].compareTo(R[j]) <= 0) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy remaining elements of L[] if any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public void sort(String arr[], int l, int r) {
if (l < r) {
int mid = l + (r - l) / 2;
sort(arr, l, mid);
sort(arr, mid + 1, r);
//run merge
merge(arr, l, mid, r);
}
}
public static void main(String[] args) {
Hack hack = new Hack();
String[] test = {"b", "a", "test2", "wow"};
hack.sort(test, 0, test.length - 1);
System.out.println(Arrays.toString(test));
}
}
Hack.main(null);
Own hack: implement merge sort in linked list
/**
* Implementation of a Double Linked List; forward and backward links point to adjacent Nodes.
*
*/
public class LinkedList<T>
{
private T data;
private LinkedList<T> prevNode, nextNode;
/**
* Constructs a new element
*
* @param data, data of object
* @param node, previous node
*/
public LinkedList(T data, LinkedList<T> node)
{
this.setData(data);
this.setPrevNode(node);
this.setNextNode(null);
}
/**
* Clone an object,
*
* @param node object to clone
*/
public LinkedList(LinkedList<T> node)
{
this.setData(node.data);
this.setPrevNode(node.prevNode);
this.setNextNode(node.nextNode);
}
/**
* Setter for T data in DoubleLinkedNode object
*
* @param data, update data of object
*/
public void setData(T data)
{
this.data = data;
}
/**
* Returns T data for this element
*
* @return data associated with object
*/
public T getData()
{
return this.data;
}
/**
* Setter for prevNode in DoubleLinkedNode object
*
* @param node, prevNode to current Object
*/
public void setPrevNode(LinkedList<T> node)
{
this.prevNode = node;
}
/**
* Setter for nextNode in DoubleLinkedNode object
*
* @param node, nextNode to current Object
*/
public void setNextNode(LinkedList<T> node)
{
this.nextNode = node;
}
/**
* Returns reference to previous object in list
*
* @return the previous object in the list
*/
public LinkedList<T> getPrevious()
{
return this.prevNode;
}
/**
* Returns reference to next object in list
*
* @return the next object in the list
*/
public LinkedList<T> getNext()
{
return this.nextNode;
}
public void setNext(LinkedList<T> next) {
this.nextNode = next;
}
// public void setNext(T data) {
// this.nextNode = new LinkedList<>(data);
// }
}
import java.util.Iterator;
/**
* Queue Iterator
*
* 1. "has a" current reference in Queue
* 2. supports iterable required methods for next that returns a generic T Object
*/
class QueueIterator<T> implements Iterator<T> {
LinkedList<T> current; // current element in iteration
// QueueIterator is pointed to the head of the list for iteration
public QueueIterator(LinkedList<T> head) {
current = head;
}
// hasNext informs if next element exists
public boolean hasNext() {
return current != null;
}
// next returns data object and advances to next position in queue
public T next() {
T data = current.getData();
current = current.getNext();
return data;
}
}
/**
* Queue: custom implementation
* @author John Mortensen
*
* 1. Uses custom LinkedList of Generic type T
* 2. Implements Iterable
* 3. "has a" LinkedList for head and tail
*/
public class Queue<T> implements Iterable<T> {
LinkedList<T> head = null, tail = null;
/**
* Add a new object at the end of the Queue,
*
* @param data, is the data to be inserted in the Queue.
*/
public void add(T data) {
// add new object to end of Queue
LinkedList<T> tail = new LinkedList<>(data, null);
if (this.head == null) // initial condition
this.head = this.tail = tail;
else { // nodes in queue
this.tail.setNextNode(tail); // current tail points to new tail
tail.setPrevNode(this.tail);
this.tail = tail; // update tail
}
}
public void addList(T[] lists) {
for (T data : lists) {
this.add(data);
}
}
/**
* Returns the data of head.
*
* @return data, the dequeued data
*/
public T delete() {
T data = this.peek();
if (this.tail != null) { // initial condition
this.head = this.head.getNext(); // current tail points to new tail
if (this.head != null) {
this.head.setPrevNode(tail);
}
}
return data;
}
/**
* Returns the data of head.
*
* @return this.head.getData(), the head data in Queue.
*/
public T peek() {
return this.head.getData();
}
/**
* Returns the head object.
*
* @return this.head, the head object in Queue.
*/
public LinkedList<T> getHead() {
return this.head;
}
/**
* Returns the tail object.
*
* @return this.tail, the last object in Queue
*/
public LinkedList<T> getTail() {
return this.tail;
}
/**
* Returns the iterator object.
*
* @return this, instance of object
*/
public Iterator<T> iterator() {
return new QueueIterator<>(this.head);
}
/**
* Returns if queue is empty
*
* @return boolean if it is empty
*/
public boolean isEmpty() {
return this.head == null;
}
/**
* Changes the head
*
*/
public void setHead(LinkedList<T> h) {
this.head = h;
}
/**
* Returns size of queue
*
* @return size of queue
*/
public int size() {
int sz = 0;
for (T e: this) {
sz++;
}
return sz;
}
public String toString() {
int count = 0;
String str = "";
for (T e : this) {
str += e + " ";
count++;
}
return "count: " + count + ", data: " + str;
}
}
abstract class Sorter<T> {
String name;
double stime;
double etime;
double difftime;
int compares;
int swaps;
public Sorter(String name) {
this.name = name;
}
abstract public Queue<T> sort(Queue<T> list, boolean verbose);
public Queue<T> sort(Queue<T> list) {
return this.sort(list, true);
}
public void start() {
this.stime = System.nanoTime();
}
public void end() {
this.etime = System.nanoTime();
}
public double elapsedtime() {
difftime = etime - stime;
return difftime;
}
public void incrementcompare() {
compares++;
}
public void incrementswap() {
swaps++;
}
public int printcomp() {
return this.compares;
}
public int printswap() {
return this.swaps;
}
}
/**
A class representing the Merge Sort algorithm for sorting a Queue of elements
@param <T> The type of elements in the Queue, must implement Comparable
*/
class Merge<T extends Comparable<T>> extends Sorter<T> {
/**
Creates a new instance of Merge Sort
*/
public Merge() {
super("Merge Sort");
}
/**
Sorts the given Queue of elements using Merge Sort algorithm
@param q The Queue of elements to be sorted
@param verbose A boolean indicating whether to print out the sorting process or not
@return The sorted Queue of elements
*/
public Queue<T> sort(Queue<T> q, boolean verbose) {
super.start();
q.setHead(mergeSort(q.getHead()));
super.end();
return q;
}
private LinkedList<T> mergeSort(LinkedList<T> head) {
// Base case: if the linked list is empty or has only one element
if (head == null || head.getNext() == null) {
return head;
}
// Find the middle node of the linked list
LinkedList<T> middle = getMiddle(head);
LinkedList<T> nextOfMiddle = middle.getNext();
middle.setNext(null);
// Recursively sort the left and right halves of the linked list
LinkedList<T> left = mergeSort(head);
LinkedList<T> right = mergeSort(nextOfMiddle);
// Merge the two sorted halves of the linked list
return merge(left, right);
}
private LinkedList<T> getMiddle(LinkedList<T> head) {
// Base case: if the linked list is empty
if (head == null) {
return head;
}
// Initialize two pointers: slow and fast
LinkedList<T> slow = head;
LinkedList<T> fast = head;
// Traverse the linked list using two pointers:
// slow moves one node at a time, while fast moves two nodes at a time
while (fast.getNext() != null && fast.getNext().getNext() != null) {
slow = slow.getNext();
fast = fast.getNext().getNext();
}
// The slow pointer is now pointing to the middle node of the linked list
return slow;
}
private LinkedList<T> merge(LinkedList<T> left, LinkedList<T> right) {
LinkedList<T> result = null;
// Base case: if one of the linked lists is empty, return the other one
if (left == null) {
return right;
}
if (right == null) {
return left;
}
// Compare the first nodes of the left and right linked lists,
// and recursively merge the remaining halves until all nodes are merged
if (left.getData().compareTo(right.getData()) <= 0) {
result = left;
result.setNext(merge(left.getNext(), right));
} else {
result = right;
result.setNext(merge(left, right.getNext()));
}
super.incrementswap();
super.incrementcompare();
return result;
}
}
public class Tester {
private static double calcAvg(ArrayList<Double> arr) {
double sum = 0;
if(!arr.isEmpty()) {
for (Double i : arr) {
sum += i;
}
return sum / arr.size();
}
return sum;
}
public static void main (String[] args) {
List<Sorter<Integer>> sorters = new ArrayList<Sorter<Integer>>();
sorters.add(new Merge<>());
int size = 5000;
for (Sorter i : sorters) {
int test = 1;
ArrayList<Double> elapsed = new ArrayList<Double>();
ArrayList<Double> comp = new ArrayList<Double>();
ArrayList<Double> swap = new ArrayList<Double>();
while (test <= 20) {
ArrayList<Integer> arr = new ArrayList<Integer>();
for (int j = 0; j < size; j++) {
int rand = (int) Math.floor(Math.random() * size * 10);
arr.add(rand);
}
Queue<Integer> q = new Queue<>();
q.addList(arr.toArray(new Integer[size]));
i.sort(q);
elapsed.add(i.elapsedtime());
comp.add(new Double(i.printcomp()));
swap.add(new Double(i.printswap()));
test++;
}
System.out.println(i.name);
System.out.printf("Average Elapsed time: %.10fs\n", calcAvg(elapsed)/1000000000);
System.out.printf("Average Number of compares: %.2f\n", calcAvg(comp));
System.out.printf("Average Number of swaps: %.2f\n", calcAvg(swap));
System.out.println();
}
System.out.println();
}
}
Tester.main(null);