Java - Stooge Sort Algorithm

Java Sorting Algorithm: Exercise-18 with Solution

Write a Java program to sort an array of given non-negative integers using the Stooge Sort Algorithm.

Stooge sort is a recursive sorting algorithm with a time complexity of O(nlog 3 / log 1.5 ) = O(n2.7095...). The running time of the algorithm is thus slower than efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort.

Sample Solution:

Java Code:

import java.util.Arrays;
 public class Stooge {
    public static void main(String[] args) {
      System.out.println("Original Array:");
        int[] nums = {7, -5, 3, 2, 1, 0, 45};
        System.out.println(Arrays.toString(nums));
        stoogeSort(nums);
        System.out.println("Sorted Array:");
        System.out.println(Arrays.toString(nums));
    }
 
    public static void stoogeSort(int[] L) {
        stoogeSort(L, 0, L.length - 1);
    }
 
    public static void stoogeSort(int[] L, int i, int j) {
        if (L[j] < L[i]) {
            int tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
        }
        if (j - i > 1) {
            int t = (j - i + 1) / 3;
            stoogeSort(L, i, j - t);
            stoogeSort(L, i + t, j);
            stoogeSort(L, i, j - t);
        }
    }
}

Sample Output:

Original Array:
[7, -5, 3, 2, 1, 0, 45]
Sorted Array:
[-5, 0, 1, 2, 3, 7, 45]

Flowchart:

Java Code Editor:

Contribute your code and comments through Disqus.

Previous: Write a Java program to sort an array of given integers Stooge Sort Algorithm.
Next: Write a Java program to sort an array of given integers using Bucket Sort Algorithm