Stooge Sort Algorithm in C

This C program sorts a given array of integer numbers using Stooge Sort technique.
Stooge sort is a recursive sorting algorithm with a time complexity of O(n^{log 3 / log 1.5}). The running time of the algorithm is thus extremely slow compared to efficient sorting algorithms, such as Merge sort, and is even slower than Bubble sort, a canonical example of a fairly inefficient and simple sort.

Here is the source code of the C program to sort integers using Stooge Sort technique. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

```
/*
```
```
 * C Program to Perform Stooge Sort
```
```
 */
```
```
#include <stdio.h>
```
```
void stoogesort(int [], int, int);
```
```
 
```
```
void main()
```
```
{
```
```
    int arr[100], i, n;
```
```
 
```

    printf("How many elements do you want to sort: ");

```
    scanf("%d", &n);
```
```
    for (i = 0;i < n; i++)
```
```
        scanf(" %d", &arr[i]);
```
```
    stoogesort(arr, 0, n - 1);
```
```
    printf("Sorted array : \n");
```
```
    for (i = 0;i < n;i++)
```
```
    {
```
```
        printf("%d ", arr[i]);
```
```
    }
```
```
    printf("\n");
```
```
}
```
```
 
```
```
 
```

void stoogesort(int arr[], int i, int j)

```
{
```
```
    int temp, k;
```
```
    if (arr[i] > arr[j])
```
```
    {
```
```
        temp = arr[i];
```
```
        arr[i] = arr[j];
```
```
        arr[j] = temp;
```
```
    }
```
```
    if ((i + 1) >= j)
```
```
        return;
```
```
    k = (int)((j - i + 1) / 3);
```
```
    stoogesort(arr, i, j - k);
```
```
    stoogesort(arr, i + k, j);
```
```
    stoogesort(arr, i, j - k);
```
```
}
```

$ gcc stoogesort.c -o stoogesort
$ ./stoogesort
 
How many numbers you want to sort: 5
 
Enter 5 numbers : 755 32 20 35 333
 
Sorted array is : 20 32 35 333 755