Sort

Mergesort VS Quicksort

Mergesort

Algorithm

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Performance

• Worst Case O(n log n)
• Average Case O(n log n)
• Worst Case Space Complexity O(n) auxiliary

Example code

public ListNode sortList(ListNode head) {
    
  ListNode node = head;
        int n =0;
        
        while(node!= null){
            n++;
            node = node.next;
        }
        
        node = head;
        
        return sortList(head, n);
        
        
    }
    
 public ListNode sortList(ListNode head, int len){
     ListNode node = head;
        ListNode pre = null;
        ListNode left = head;
        ListNode right = null;
        
        if(len<2) return head;
        
   for(int i=1; i<=len/2; i++){
             pre = node;
             node = node.next;
      }
         
        pre.next = null;
        right = node;
        
        left = sortList(left, len/2);
        right = sortList(right, len-len/2);
        
        return mergeList(left, len/2,  right, len-len/2);
 }
    
    public ListNode mergeList(ListNode left, int leftLen, ListNode right, int rightLen){
     ListNode newListHead = null;
     ListNode node = null;
     ListNode leftNode = left, rightNode = right;
         
     if(left.val > right.val){
      newListHead = right;
      right = right.next;
      rightLen--;
      rightNode = right;
     }
     else{
      newListHead = left;
      left = left.next;
      leftLen--;
      leftNode = left;
     }
     
     node = newListHead;
      
     while(leftLen>0 || rightLen>0){
      
      if(leftLen>0 && rightLen>0){
       if(leftNode.val > rightNode.val){
        node.next = rightNode;
        rightNode = rightNode.next;
        rightLen--;
        node = node.next;
        node.next = null;
        
       }
       else{
        node.next = leftNode;
        leftNode = leftNode.next;
        leftLen--;
        node = node.next;
        node.next = null;
       }
      }
      else if(leftLen == 0){
       node.next = rightNode;
       break;
      }
      else if(rightLen == 0){
       node.next = leftNode;
       break;
      }
      
     }
     
     return newListHead;
    }

Reference wikipedia Mergesort

Quicksort

Algorithm

Quicksort is a divide and conquer algorithm. Quicksort first divides a large list into two smaller sub-lists: the low elements and the high elements. Quicksort can then recursively sort the sub-lists. The steps are:

1. Pick an element, called a pivot, from the list.
2. Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
3. Recursively apply the above steps to the sub-list of elements with smaller values and separately the sub-list of elements with greater values. The base case of the recursion are lists of size zero or one, which never need to be sorted.

Performance

• Worst Case O(n2)
• Average Case O(n log n)
• Worst Case Space Complexity O(n) auxiliary (naive) or O(log n) auxiliary

Example code

public void sort(int[] num, int start, int end){  
    int pivotIdex = partition(num, start, end);
    
    if(start < pivotIdex-1)
     sort(num, start, pivotIdex-1);
    if(pivotIdex<end)
        sort(num, pivotIdex, end);   
   }
   
public int partition(int arr[], int left, int right){    
         int i = left, j = right;
         int tmp;
         int pivot = arr[(left + right) / 2];
         while (i <= j) {
               while (arr[i] < pivot)
                     i++;
               while (arr[j] > pivot)
                     j--;
               if (i <= j) {
                     tmp = arr[i];
                     arr[i] = arr[j];
                     arr[j] = tmp;
                     i++;
                     j--;
               }
         };
         return i;   
   } 

Comparison

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n). On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays. On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.
As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted.[11] Python uses timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE 7,[12] on the Android platform,[13] and in GNU Octave.[14]
Reference WikiPedia Quicksort