Mergesort

Merge sort is an algorithm that can be defined crisply in a recursive manner. We take a look a how to reason about Merge Sort and its recursive split steps. We also look at the linear time merge step and give the overarching algorithm a full analysis.

Table of Contents
Enroll in our 5-day mini coding interview class

Code Sample

/*
Sort List - LeetCode: https://leetcode.com/problems/sort-list/
This code passes all Leetcode test cases as of Sept. 28 2019
*/
// The split subroutine
public ListNode sortList(ListNode head) {
/*
Base case, an empty list or a single item list. That is a sorted list,
hence we just return the list (it is either empty or only has 1 item)
*/
if (head == null || head.next == null) {
return head;
}
// Abstracting out finding the middle node
ListNode mid = getMiddleAndSplitInHalf(head);
/*
Sort the left. Sort the right. This is recursive splitting and handing
responsibility off
*/
ListNode leftHalf = sortList(head);
ListNode rightHalf = sortList(mid);
// Merge the sorted left half and sorted right half
return merge(leftHalf, rightHalf);
}
/*
The merge subroutine
*/
private ListNode merge(ListNode l1Pointer, ListNode l2Pointer) {
ListNode dummyHead = new ListNode(0);
ListNode endOfSortedList = dummyHead;
// While neither list has been exhausted keep doing comparisons and rewirings
while (l1Pointer != null && l2Pointer != null) {
if (l1Pointer.val < l2Pointer.val) {
// Where l1 points gets the placement
endOfSortedList.next = l1Pointer;
l1Pointer = l1Pointer.next;
} else {
// Where l2 points gets the placement
endOfSortedList.next = l2Pointer;
l2Pointer = l2Pointer.next;
}
/*
The 'endOfSortedList' is now the item we just tacked to
the end, move the pointer there
*/
endOfSortedList = endOfSortedList.next;
}
// If we exhaust one list, just tack the other to the end of the sorted list
if (l1Pointer != null) {
endOfSortedList.next = l1Pointer;
}
if (l2Pointer != null) {
endOfSortedList.next = l2Pointer;
}
/*
The head of the merged list is the .next of the dummy head, the dummy head
helped us protect against the empty state the list was in to start
*/
return dummyHead.next;
}
// Get the middle node and split the linked list in half
private ListNode getMiddleAndSplitInHalf(ListNode head) {
ListNode prev = null;
ListNode slow = head;
ListNode fast = head;
/*
slow pointer, 1 hop per iteration
fast pointer, 2 hops per iteration
When 'fast' reaches the last element or runs over the list the 'slow'
pointer will point to the middle of the list
*/
while (fast != null && fast.next != null) {
// Keep prev 1 behind where slow will be. We want this for later
prev = slow;
// Move the slow and fast pointers
slow = slow.next;
fast = fast.next.next;
}
/*
Cut off the end of the first half list so it is no longer connected
in memory to the right half list head
We kept track of prev to be able to do this cutoff
*/
prev.next = null;
// 'slow' sits at the middle of the list
return slow;
}
view raw MergeSort.java hosted with ❤ by GitHub