Merge Sort Algorithm

• Merge sort and Quick sort are discussed.
• Merge Sort is covered before Quick Sort.

Merge Sort

• A recursive sorting algorithm using the "divide and conquer" approach.
• Top-down merge sort is recursive
• Divides the array into two halves.
• Sorts each array recursively.
• Merges the arrays.

Bottom Up Merge Sort

• Iterative.
• Iterates through the array.
• Merges subarrays of size 1, then size 2, 4, 8, and so on.
• Merging requires an auxiliary array for extra space.

Top Down Merge Sort Java Implementation

• The methods needed are:
  • A public method that passes in the array to be sorted
  • A public static void sort (Comparable [] a)
  • A recursive method that has passes of the original and auxiliary arrays, and indices of the subarray to be sorted
  • private static void sort (Comparable [] a, Comparable [] aux, int lo, int hi)
  • A merge method, to merge sorted subarrays, with the 2 arrays to be merged, lowest, highest and midpoint indices
  • private static void merge (Comparable [] a, Comparable [] aux, int lo, int mid, int hi)
• An auxiliary array of the same size of the original array is created
• Recursion kicks off by passing in 0 and array length-1 as indices (ie the full original array)
• Recursion is repeated untill lo and hi are equal to get to array of length 1

Recursive Method

• Note: mid = lo+ (hi-lo)/2 avoids integer overflow.
• Merge method involves copying the original array into auxiliary array, then merging elements back into the original one in sorted order

Merge Sort Running Time

• A laptop executes 10^8 compares/second
• A supercomputer executes 10^12 compares/second
• Number of compares is less than N lg N.
  • It is Linearithmic.
  • Applies to both average and worst cases.
  • Is Stable – the "less than" operator favours the left hand value to right hand one even when they're equal.
• Number of array accesses is less than 6 N lg N.
• Memory use relies on an auxiliary array of size N.

Merge Sort Improvements

• Cut off to insertion sort is used for ~10 items to avoid too much overhead for small subarrays

Merge Sort Further Improvements

• Improve if largest item in first half is smaller than smallest in second half to stop if already sorted.
• Switch the roles of aux[] and a[]
• Eliminates the time taken to copy to the auxiliary array used for merging, but does not affect the space used.
• Uses 2 invocations of the sort method.
  • Takes input from the given array and puts the sorted output in the auxiliary array
  • Takes its input from the auxiliary array and puts the sorted output in the given array.

Merge Sort - Bottom Up

• Passes through array merging subarrays of size 1, 2, 4, etc
• Adaptive sort, combination of
• Natural merge sort: exploits pre-existing order by identifying naturally occurring non-descending sequences (so ascending or equal) and searches for at least 2 elements
• insertion sort is used to make initial runs
• Timsort is used in Java 7 onwards (for non-primitive data types), Python, and Android

Quick Sort

• One of top 10 algorithms of 20th century in science and engineering.
• Invented by Tony Hoare in 1959
• Steps
• Shuffle the array
• Partition the array
• S − {v} is partitioned into two disjoint subsets: S1 = {all values x ≤ v} and S2 = {all values x ≥ v}
• S1 is the left side of the array
• S2 is the right side of the array
• Sort each subarray recursively

Quick Sort Details

• Implement partitioning recursively
• Pick a pivot
  • Want a value that will cause |S1| and |S2| to be non-zero, and close to equal in size if possible
• Deal with cases where the element equals the pivot

Quick Sort - Picking a Pivot

• Ideally it would be the median value
• Pivot options:
  • Pick the first element, which is the simplest
  • Ok if array shuffled, bad if array sorted (worst case for quicksort)
  • Choose pivot randomly, which uses a random number generator
  • Approximate: choose a median of first, middle and last value, which is more expensive, calculating median

Quick Sort - Partitioning

• It is necessary to partition the array into left and right sub-arrays
• The elements in left sub-array are less than or equal to the pivot
• The elements in right sub-array are greater than or equal to the pivot
• Elements get to the correct partition by choosing an element from the array as the pivot and making one pass through the rest of the array and swap as needed to put elements in partitions.

Quick Sort Recursive Code

• Uses random numbers to decide what to do next somewhere in its logic

Quick Sort Performance

• Make sure to shuffle the array at the start or pick a random pivot in each subarray to avoid worst case performance
• Home PC executes 10^8 compares/second, whilst a supercomputer executes 10^12 compares/second.
• Expected number of compares in average case is ~ 1.39 n lg n, which is 39% more compares than mergesort, but is faster than mergesort in practice because of less data movement.
• Properties Summary
• Not stable because of long distance swapping.
• No iterative version (without using a stack).
• Pure quicksort is not good for small arrays.
• "In-place", it uses auxiliary storage because of recursive call (O(logn) space).
• Time complexity is O(n log n) average case performance, but O(n²) worst case performance.
• Improvements
  • Use insertion sort for small arrays Cut off to insertion sort at subarray size ~10
  • Use median for pivot value (median of 3 random items, ie first, last, middle)
  • 3-way quicksort, dual pivot, 3-pivot
• Stop at equal keys to avoid problem if all items equal to pivot are moved to one side, which causes the consequence of ~1/2 n^2 compares when all keys are equal
• Stop scanning if keys are equal. This results in the keys dividing the array exactly
• A 3-way partitioning can be used

Three Way Partitioning

• Partition array into three parts so that:
  • Entries in between lt and gt equal to the partition item.
• No larger entries to the left of lt.
• No smaller entries to the right of gt.
• Lets you stop scanning if keys are equal
• Is a Dutch national flag problem using Edsger Dijkstra's solution

2 Pivot Quick Sort

• Partitions with Keys less than p1, Keys between p1 and p2, and Keys greater than p2.
• Recursively sort three subarrays

3 Pivot Quick Sort

• Has keys grouped into less than p1, between p1 and p2, between p2 and p3 and greater than p3

Quick Sort - Cache Improvements

• The Principle of locality:
• the same values, or related storage locations, are frequently accessed
• Temporal locality
• If at one point a particular memory location is referenced, then it is likely that the same location will be referenced again in the near future
• Spatial locality
  • If a particular storage location is referenced at a particular time, then it is likely that nearby memory locations will be referenced in the near future -> pre-fetch arrays
• Implemented through caching to store data "nearer" to processor, 2-pivot and 3-pivot have smaller number of cache misses and recursive calls

Merge Vs Quick

• In Java, Arrays.sort() uses QuickSort for sorting primitives and MergeSort for sorting Arrays of Objects.
  • This is because merge sort is stable, so it won't reorder elements that are equal.
• QuickSort in java is 2-pivot since 2009
• MergeSort in java is Timsort

Sort Algorithms Summary

• System sort - Arrays.sort(); is usually good enough
• Compare performance to system sort in assignment

Comparator Interface

• Has a Comparable interface
  • Can override compareTo() method
• Uses multiple classes implementing Comparator and override compare.
  • Allows users to create custom orders in system sorts (pass as a second argument to Array.sort(a, new MyCustomOrder());)