title: Quicksort Stability Demo
body: <p>I understand that quicksort is indeed unstable (incase of primitives)because of the way partitioning works/long-distance exchanges. I am trying to understand what happens if quicksort is used to sort complex objects with equal keys. Essentially why java <code>Collections.sort</code> doesn't use Quicksort. </p>
  
  <p>Here is a demo app that I created to aid my understanding. As per this app, objects with equal keys seem to retain their input order. I know that I have some understanding gaps here. I did search on the web but most examples are based on integer sorting. </p>
  
  <p>Please help me understand quicksort stability issues.</p>
  
  <blockquote>
    <p><strong>DEMO</strong></p>
  </blockquote>
  
  <pre><code>import java.util.*;
  
  public class QuickSortStabilityDemo {
  
      static class Node implements Comparable&lt;Node&gt; {
          String name;
          int rank;
  
          public Node(String name, int rank) {
              this.name =  name;
              this.rank = rank;
          }
  
          @Override
          public int compareTo(Node o) {
              int result = this.name.compareTo(o.name);
              if(result == 0) {
                  return this.rank == o.rank ? 0 : this.rank &lt; o.rank ? -1: 1;
              }
              else {
                  return result;
              }
          }
  
          @Override
          public String toString() {
              return "{" + this.name + "," + this.rank + "," + this.hashCode() + "}" ;
          }
      }
  
      //Fisher-Yates 
          public void shuffleArray(Node[] arr) {
              Random random = new Random();
              int n = arr.length;
  
              for(int i=n-1; i&gt;=0; i--) {
                  int j = random.nextInt(i+1);
                  Node temp = arr[i];
                  arr[i]= arr[j];
                  arr[j]=temp;
              }
  
          }
  
          private void swap(Node[] arr, int i, int j) {
              Node temp = arr[i];
              arr[i] = arr[j];
              arr[j] = temp;
          }
  
          public void sort(Node[] arr, int start, int end) {  
  
              if(start &gt;= end) {
                  return;
              }
  
  
  
              Node pivot = arr[start];
  
              int lt = start;
              int gt = end;
  
  
              for(int current=start+1;current &lt;= gt; ) {
  
                  if(arr[current].compareTo(pivot) &lt; 0) {
                      swap(arr,current,lt);  
                      current++; 
                      lt++; 
                  }
                  else if(arr[current].compareTo(pivot) &gt; 0) {
                      swap(arr,current,gt); 
                      gt--; 
                  }
                  else {
                      current++;
                  }
  
              }
              sort(arr,start,lt-1);
              sort(arr,gt+1,end);
  
  
          }
  
          public static void main(String[] args) {
              QuickSortStabilityDemo sort = new QuickSortStabilityDemo();
              String[] cities = {"New York","Jersey City","Pittsburgh"};
  
              List&lt;Node&gt; list = new ArrayList&lt;&gt;();
  
              for(int i=0;i &lt;3;i++) {
                  for(int j=1; j &lt;=3; j++) {
                      list.add(new Node(cities[i],i));
                  }
              }
  
              Node[] arr = list.toArray(new Node[list.size()]);
  
              System.out.println("Before sorting...");
  
              System.out.println(Arrays.toString(arr));
  
              sort.sort(arr,0,arr.length-1);
  
              System.out.println("After sorting...");
  
  
              System.out.println(Arrays.toString(arr));
          }
  
  }
  </code></pre>