algorithm - Quick Sort 3-way Partitiion -

i'm trying implement quick sort algorithm 3-way partition technique, using "m1" , "m2" indexes delimitate zone elements equal pivot. here code:

public class sorting { private static random random = new random();  private static int[] partition3(long[] a, int l, int r) {     long x = a[l];     int m1 = l;     int m2 = l;      (int = l + 1; <= r; i++) {         if (a[i] < x) {             m1++;             m2++;             swap(a, m1, m2);          }          if (a[i] == x) {             m2++;             swap(a, i, m1);         }     }     swap(a, l, m1);       int[] m = {m1, m2};     return m; }  private static void swap(long[] a, int i, int j) {     long temp = a[i];     a[i] = a[j];     a[j] = temp; }  private static void randomizedquicksort(long[] a, int l, int r) {     if (l >= r) {         return;     }     int k = random.nextint(r - l + 1) + l;     long t = a[l];     a[l] = a[k];     a[k] = t;     int m[] = partition3(a, l, r);     randomizedquicksort(a, l, m[0] - 1);     randomizedquicksort(a, m[1] + 1, r); }  public static void main(string[] args) {     scanner scanner = new scanner(system.in);     int n = scanner.nextint();     long[] = new long[n];     (int = 0; < n; i++) {         a[i] = scanner.nextlong();     }     randomizedquicksort(a, 0, n - 1);     (int = 0; < n; i++) {         system.out.print(a[i] + " ");     } }  } 

most of times outputs right answer tests, doesn't. can tell me i'm doing wrong?

your code fails cases when have repeating numbers in list. instance, code fails test case:

1 2 1 3 1

it return different every time due random number generation, won't correct answer. issue partition3() function, cases within loop, decide increment , flip. in case:

if (a[i] < x) {     m1++;     m2++;     swap(a, m1, m2); } 

you missing swap moves i'th index proper place. swap so:

if (a[i] < x) {     m1++;     m2++;     swap(a, m1, m2);     swap(a, m1, i); //the missing swap. } 

in other if-condition, missing 2 things. first of all, should else-if, avoid unintended entering of both if-conditions. second of all, swap @ wrong location. should swap @ m2 (the second wall), not @ m1. because second wall takes care of values same pivot, not first. corrected, second if-condition so:

else if (a[i] == x) { //note addition of else     m2++;     swap(a, i, m2); //corrected, swaps @ m2 } 

with these corrections, code seems work intended.