Odd-Even Sort is a headstrong little girl.  

The middle daughter of Heap Sort and Cocktail Shaker Sort, she has recently discovered she a particular skill, a skill that makes her a nightmare to people like her parents. This skill has allowed her to get extra dessert, more screen time, even less chores; in short, everything a ten-year-old middle child could ever dream of.

That skill? Getting one parent to say yes when the other already said no.

She's sneaky about it. She will wait minutes, hours even, just to strike the unsuspecting parent at exactly the right moment. She knows just when her opportunity arises: when mom gets home from work, when dad is dealing with her baby brother Bogosort, when her elder sister Counting Sort needs to get to soccer practice. All her life she's been perfecting this skill, and now she's a master.

Here's hoping she uses her powers for good. Or at least extra ice cream.

Cheers! Photo by Mark Cruz / Unsplash

The Rundown

exceptionnotfound/SortExtravaganzaCSharp
Lots of example sorting algorithms, from a family reunion. - exceptionnotfound/SortExtravaganzaCSharp
GitHubexceptionnotfound

Algorithm

  1. FOR each item in an odd numbered position
  2. COMPARE that item against the item in the next-highest position.
  3. IF the elements are out of order, SWAP them.
  4. FOR each item in an even-numbered position
  5. COMPARE that item against the item in the next-highest position.
  6. IF the elements are out of order, SWAP them.
  7. GOTO 1, CONTINUE until list is sorted.

Visualization

The base visualization from Wikipedia is cool to look at but doesn't help me understand this algorithm at all. So let's demonstrate the algorithm with a simple set of numbers. Here's our unsorted collection:

{ 15, 62, 42, 29, 17 }

On the first pass of the algorithm, in the first step, we compare the element in position 1 against the element in position 2. Position 1 is 15, position 3 is 62, so these are in order.

The next comparison is between position 3 (42) and position 4 (29). Those elements are out of order, so the algorithm swaps them, resulting in:

{ 15, 62, 29, 42, 17 }

The next move would compare the element in position 5 against the one in position 6, but since there isn't one in position six, the algorithm instead switches to doing the even-numbered comparison.

The first even comparison (position 2 to position 3) results in:

{ 15, 29, 62, 42, 17 }

The second even comparison results in:

{ 15, 29, 62, 17, 42 }

Now we go back to the odd-numbered comparisons:

{ 15, 29, 17, 62, 42 }

Now back to even-numbered:

{ 15, 17, 29, 62, 42 }
{ 15, 17, 29, 42, 62 }

And now the array is sorted! It took us four passes to do this, and if you're thinking that seems pretty inefficient, you are not wrong.

Here's the audibilization of this algorithm:

C# Implementation

class OddEvenSort
{
    public static void Sort(int[] array, int length)
    {
        bool isSorted = false;

        while (!isSorted)
        {
            isSorted = true;

            //Swap i and i+1 if they are out of order, for i == odd numbers
            for (int i = 1; i <= length - 2; i = i + 2)
            {
                if (array[i] > array[i + 1])
                {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    isSorted = false;
                }
            }

            //Swap i and i+1 if they are out of order, for i == even numbers
            for (int i = 0; i <= length - 2; i = i + 2)
            {
                if (array[i] > array[i + 1])
                {
                    int temp = array[i];
                    array[i] = array[i + 1];
                    array[i + 1] = temp;
                    isSorted = false;
                }
            }
        }
        return;
    }

    public static void Main()
    {
        int[] array = { 71, 42, 19, 3, 33, 28, 0, 89, 44, 2, 81 };
        int length = array.Length;

        CommonFunctions.PrintInitial(array);

        Sort(array, length);

        CommonFunctions.PrintFinal(array);

        Console.ReadKey();
    }
}

Time and Space Complexity

Given that Odd-Even sort is a derivative of Bubble Sort, we would expect the worst-case time complexity to be similar, and indeed it is; for both algorithms it is O(n2). The best-case scenario for Odd-Even sort is remarkably better at O(n), though, and the space complexity is constant at O(1). However, most of the time we as programmers only care about the worst-case, and in that regard Odd-Even sort is not better than some of the other, more modern algorithms we've seen.

Summary

Odd-Even Sort, being a derivative of Bubble Sort, is not known to be an efficient algorithm. That said, it has some uses in specific cases (as seen on its Wikipedia page), so it's not totally without merit. Plus, she's really good at getting extra dessert. Maybe, if you're nice to her, she'll share with you.

The soccer star of the family, Counting Sort, is next up. She needs some help from the others to achieve her dream.

Counting Sort in C#
Counting Sort is the star athlete of the family, even more so than Comb Sort. A soccer striker with a knack for faking out the keeper, she scores goals likefootball linebackers down calories. She’s been playing since she could walk;soccer is all she wants to do. She’s even got a potential schol…
Exception Not FoundMatthew Jones

Don't forget to check out the sample project over on GitHub!

Happy Coding!