CareerCup

Hi, Eugene. Thanks for the kick in the head. I see that it's a single problem now :-) In the 1st test case, removal of the edge 2,1 yields two subtrees of weight 15 and 8 respectively w/difference = 7. In the 2nd test case, removal of edge 3,1 yields subtrees of weight 14 and 27 w/difference = 13. So, now I at least understand the problem and what's being asked. Off to code it up. Thanks again - C

This seems like TWO good but unrelated questions. Or, I am I overtired?

How to find min-weight (coin) in a given set of '10' distinct weights (coins) in minimum number of weighing's if provided with a balance. (no labels shown on coin resembling the weight). Generalize for 'n' distinct weights.

^-- I hate problems that are stated ambiguously.

"How to find the min-weight (coin)" => implies there's a coin in the set that weights less than the others coins in the set. Stated alternately, this implies there are two different types of coins (i.e. two possible weights for each specific coin in the set) and nine of the ten coins are of heavier variety while the remaining one is of lighter variety. But it's not clear that's what's being asked at all...

"... Given a set of '10' distinct weights (coins)" => ambiguous. could mean there are ten coins in the set each of which has a distinct weight (i.e. each coin in the set of ten has a different (i.e. distinct) weight) or there are ten coins in the set which each has a weight which could be the same or different. (would seem like an imprecise or unusual connotation of the word 'distinct'. Reading on...

"Generalize for n distinct weights" => here we use the term 'distinct' again. It's still unclear what the problem statement is. Are we saying there are n different types of coins each with a distinct weight and the task is to deduce the minimum weight coin from a set of m coins (e.g. m == 10). Or, is the question to scale the answer as the set size of coins is increased to n coins (saying nothing about how many different coin types (i.e. distinct weights) there are?

So...
Assume a set comprising C coins total.
The set of C coins comprises coins chosen from another set T whose members are archetypes (e.g. T might comprise pennies, nickles, dimes, quarters). Each member of T has a distinctly different weight.

What is the size of set C and the size of set T? Are there any assumptions about the composition of C given T? Or, is C simply chosen from random from T?

This is a great problem. I really don't like (or perhaps don't fully comprehend) the answers given on this thread. Let's dig deeper on this one and explore:

Problem restatement:
There exists an alphabet comprising some number of characters.
The order of the alphabet, i.e. the full-ordering, is not known.
You are given a list of "words" comprised of characters from the alphabet.
The list of words is given to be sorted in lexicographical order.
Write a program to deduce the order of the alphabet.

For the sake of example, let's assume that we're using an English alphabet (i.e. we know the full order). Now assume we have a set of words sorted in ascending lexicographical order:

aardvark
ant
bee
cat
cow
dog
horse
llama
sheep
zebra

Given that we know the order of the English alphabet, it's easy to see that the list of animals comprising our input data is correctly sorted.

Now forget that you know anything at all about the English alphabet. Erase from your mind the fact that you know which characters comprise the alphabet (the problem statement doesn't bound the set of characters or make any guarantee that the set of words use all characters in the alphabet). Also, erase from your mind the fact that you know the order of the English alphabet.

Let's take the first word "aardvark". What does this tell us? It tells us that the characters "a", "r", "d", "v", and "k" are present in the alphabet. Does it provide any information that can be used to establish the order of these characters? NO! Remember that it's the order of the words in the list and thus comparisons between adjacent words in the list that provides clues about the order of the alphabet.

Okay, now let's look at the first and second words:

aardvark
ant

What does this tell us? We see two new characters "n" and "t" by inspection of "ant". What's more we notice that the characters in the first column are both "a". So clearly the lexicographical ordering of these two words wasn't decided on the basis of the first column. Looking at the second column we note that the characters are different and correctly conclude that in our alphabet "a" proceeds "n".

How about the third column? Sorry, no more clues here. We know that the order of "aardvark" and "ant" was decided on the basis of the second column character and cannot deduce anything further by comparing the third column.

So on we go through the list of animal words... Below I've reproduced the lexicographically sorted list of words in the left column, and indicate the "clues" in the right column. For simplicity I'm not going to list new characters discovered in the alphabet but rather focus only on clues about the order of the characters in the alphabet.

Note that because you actually do know the order of the English alphabet, you can easily vet this information without doing insane mental gymnastics. Also note that by convention an order clue is indicated by an ordered pair representing an edge in a directed graph. For example (a,b) indicates a directed edge from tail vertex "a" to head vertex "b" indicating that "a" proceeds "b" in the alphabet.

aardvark no order clues
ant (a,n) based on column 2
bee (a,b) based on column 1
cat (b,c) based on column 1
cow (a,o) based on column 2
dog (c,d) based on column 1
horse (d,h) based on column 1
llama (h,l) based on column 1
sheep (l,s) based on column 1
zebra (s,z) based on column 1
n
/
a -> b -> c -> d -> h -> l -> s -> z
\
o

Now remember that you know the order of the English alphabet and vet this graph. Makes sense right? For example we know that "n" comes after "a" as does "b" and "o". And clearly a -> b -> c -> d -> h -> l -> s -> z is correctly ordered.

Note that given our sorted list of animals we do not know the order of "b", "n" and "o". All we know is that they follow "a".

Also note that there are bunch of characters used in our list of animal words for which no clues were found. These are not show in the ASCII graph above. But these are really in the graph too (all with zero in-degree).

I seriously question the utility of doing a topological sort... It would produce a somewhat interesting result BUT is essentially meaningless except in the case that every vertex has out-degree one.

You could imagine a system that attempts to deduce ordering on an alphabet that exposes an interface DoesXProceedY(x, y) which returns YES, NO or KNOWN. Such a system could not (in general) use a topological sort of the graph to deduce the correct answer. Instead, it would need the graph topology.

Hope this helps.

I too am highly suspicious of mpmaster's answer.

If the first "word" is "$*" and the second word is "!&" and they're lexicoographically sorted in ascending order (i.e. "$*" < "!&") then it's simply impossible for "!" to appear before "$" in the alphabet order as asserted.

Given the five input "words" and order specified there's not enough data to establish a full ordering of the alphabet as I understand it.

The input data does allow you to deduce a partial ordering which is "$!*&#". There's not enough information to determine the order of "@" (which is what I think you meant by "%" in the alphabet set specified).

Is the following an accurate re-statement of the problem?

There exists an alphabet comprising some number of characters.
The order of the alphabet, i.e. the full-ordering, is not known.
You are given a list of "words" comprised of characters from the alphabet.
The list of words is given to be sorted in lexicographical order.
Write a program to deduce the order of the alphabet.

Bonus:
1. What is the space/time complexity of your algorithm?
2. Given the problem statement, is it possible to deduce the full (complete) order of the alphabet? Explain your answer in detail.

I didn't initially see this but do now and agree with you. A generalized swap can be implemented using at most two reverse operations as you suggest (one if distance < 3). So O(1) best case and worst 2 * O(1) per swap.

If we presume a more general swap based on O(1) read and write operations it would seem that swap is always 4 * O(1) + a temporary variable needed to cache the first read. So swap based on reverse will definitely save time and space (presuming that it's really O(1) via dedicated hardware for example).

Interesting question if there are sort algorithms specifically optimized to take advantage of O(1) reverse. I don't know the answer (using this question to re-familiarize myself w/details of sort algorithms as I've gotten lazy and generally re-use other people's libraries these days).

I woke up agreeing with you: it's trivial to implement swap(x,y) using reverse. In the trivial case (distance = 1 or 2) a single reverse suffices. In the general case (distance > 2) two reverse operations suffices. Given this, implementing quicksort is straight forward.
I note that another poster already posted this observation below. Also suspect this is what you were implying in your original comment.
Good question.

understood but you're still not addressing the question which asks how to sort the external array.

I'll need to think about this suggestion some more. reverse(x,y) is a swap of x and y only then (y-x) < 3 so initial thinking was that any sort that depends on a true swap(x,y) would get kind of complicated. maybe I missed something. Do you agree with my space/time estimates BTW?

Here's what I came up with:

Algorithm overview:
Each element in the array is examined in turn from left to right (excluding the last element).

Upon examination of the nth element value, all the values that appear to its right are examined left to right (including the last element). This can be thought of as an outer and inner loop with the outer loop element index denoted 'o' and the inner loop index denoted 'i'. Note that o < i by definition.

If get(o) > get(i) then reverse(o, i).

Consider simple input array {2,1}:
Outer loop iterates from 0 to 0, inner loop iterates from 1 to 1
get(o==0) > get(i==1) --> reverse(0,1) --> {1,2} done

Consider input array {3,2,1,0}:
Outer loop iterates from 0 to 2, inner loop iterates from n+1 to 3.
o=0, i=1 :: {2,3,1,0} <= reversed [0,1]
o=0, i=2 :: {1,3,2,0} <= reversed [0,2]
o=0, i=3 :: {0,2,3,1} <= reversed [0,3] -- note that o=0 element is now sorted
o=1, i=2 :: {0,2,3,1} <= no reverse
o=1, i=3 :: {0,1,3,2} <= reverse [1,3] -- note that o=1 element is now sorted
o=2, i=3 :: {0,1,2,3} <= reverse [2,3] -- note that o=2 element is now sorted
also note that o=3 element doesn't need to be examined

CODE:

// C++ on WIndows
#include "stdafx.h"
#include <iostream>
#include <crtdbg.h>

using namespace std;

int input[] = {3,2,1,0};

int const array_size = ((sizeof(input) / sizeof(int)) - 1);

int total_gets = 0;
int total_reverses = 0;

// Per problem statement get is O(1)
int get(int index) {
    total_gets++;
    return input[index];
}

// Per problem statement reverse is O(1) (even though it's not here)
void reverse(int start, int end)
{
    _ASSERT(end >= start);
    _ASSERT(start >= 0);
    _ASSERT(end <= array_size);
    total_reverses++;
    int loop_range = (end - start) / 2;
    for (int i = 0 ; i <= loop_range ; i++)
    {
        int const index_start = start + i;
        int const index_end = end - i;
        int x = input[index_start];
        input[index_start] = input[index_end];
        input[index_end] = x;
    }
}

void print_array()
{
    cout << "{";
    for (int i = 0 ; i <= array_size ; i++)
    {
        cout << input[i];
        if (i != array_size)
            cout << ", ";
    }
    cout << "}";
}


// Note that the outer loop is implemented via recursion
void sort(int & recursions, int start, int end)
{
    recursions++;

    int start_val = ::get(start);

    // Inner loop
    for (int x = start + 1 ; x <= end ; x++)
    {
        int x_val = ::get(x);
        bool reverse_operation = false;
        cout << recursions << " | " << start << " | " << x << " :: ";
        if (start_val > x_val)
        {
            reverse_operation = true;
            ::reverse(start, x);
            start_val = ::get(start);
        }
        print_array();
        if (reverse_operation)
            cout << " <-- reversed [" << start << ", " << x << "] (inclusive)" << endl;
        else
            cout << " <-- no reverse" << endl;
    }
    cout << endl;
    if ((start + 1) < end)
        ::sort(recursions, start+1, end);
}


int _tmain(int argc, _TCHAR* argv[])
{
    _ASSERT( ((sizeof(input) / sizeof(int)) - 1) == array_size );

    cout << "INITIAL INPUT:" << endl;
    print_array();
    cout << endl << endl;

    int recursions = 0;
    sort(recursions, 0, array_size);

    cout << "FINAL OUTPUT:" << endl;
    print_array();
    cout << endl << endl;

    cout << "Array elements == " << (array_size + 1) << endl;
    cout << "Total get operations == " << total_gets << endl;
    cout << "Total reverse operations == " << total_reverses << endl;
    int const total_o1_ops = total_gets + total_reverses;
    cout << "Total O(1) operations == " << total_o1_ops << endl;
    cout << "Total elements squared == " << (array_size + 1) * (array_size+1) << endl;

    cout << "Total recursive invocations of sort == " << recursions << endl;


	return 0;
}

Given input array:
int input[] = {96, 5, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47};

Program output is:
INITIAL INPUT:
{96, 5, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47}

1 | 0 | 1 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 1] (inclusive)
1 | 0 | 2 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 3 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 4 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 5 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 6 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 7 :: {5, 96, 10, 5000, 2001, 7, 19, 23, 3, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 8 :: {3, 23, 19, 7, 2001, 5000, 10, 96, 5, 2, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 8] (inclusive)
1 | 0 | 9 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [0, 9] (inclusive)
1 | 0 | 10 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 11 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 12 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 13 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 14 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 15 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 16 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 17 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
1 | 0 | 18 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse

2 | 1 | 2 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 3 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 4 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 5 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 6 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 7 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 8 :: {2, 5, 96, 10, 5000, 2001, 7, 19, 23, 3, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 9 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [1, 9] (inclusive)
2 | 1 | 10 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 11 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 12 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 13 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 14 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 15 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 16 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 17 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
2 | 1 | 18 :: {2, 3, 23, 19, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse

3 | 2 | 3 :: {2, 3, 19, 23, 7, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 3] (inclusive)
3 | 2 | 4 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 4] (inclusive)
3 | 2 | 5 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 6 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 7 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 8 :: {2, 3, 7, 23, 19, 2001, 5000, 10, 96, 5, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 9 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [2, 9] (inclusive)
3 | 2 | 10 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 11 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 12 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 13 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 14 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 15 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 16 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 17 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
3 | 2 | 18 :: {2, 3, 5, 96, 10, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse

4 | 3 | 4 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [3, 4] (inclusive)
4 | 3 | 5 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 6 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 7 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 8 :: {2, 3, 5, 10, 96, 5000, 2001, 19, 23, 7, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 9 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- reversed [3, 9] (inclusive)
4 | 3 | 10 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 11 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 12 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 13 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 14 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 15 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 16 :: {2, 3, 5, 7, 23, 19, 2001, 5000, 96, 10, 9, 11, 32001, 77, 79, 91, 2012, 6, 47} <-- no reverse
4 | 3 | 17 :: {2, 3, 5, 6, 2012, 91, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [3, 17] (inclusive)
4 | 3 | 18 :: {2, 3, 5, 6, 2012, 91, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse

5 | 4 | 5 :: {2, 3, 5, 6, 91, 2012, 79, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 5] (inclusive)
5 | 4 | 6 :: {2, 3, 5, 6, 79, 2012, 91, 77, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 6] (inclusive)
5 | 4 | 7 :: {2, 3, 5, 6, 77, 91, 2012, 79, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 7] (inclusive)
5 | 4 | 8 :: {2, 3, 5, 6, 77, 91, 2012, 79, 32001, 11, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 9 :: {2, 3, 5, 6, 11, 32001, 79, 2012, 91, 77, 9, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 9] (inclusive)
5 | 4 | 10 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- reversed [4, 10] (inclusive)
5 | 4 | 11 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 12 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 13 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 14 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 15 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 16 :: {2, 3, 5, 6, 9, 77, 91, 2012, 79, 32001, 11, 10, 96, 5000, 2001, 19, 23, 7, 47} <-- no reverse
5 | 4 | 17 :: {2, 3, 5, 6, 7, 23, 19, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [4, 17] (inclusive)
5 | 4 | 18 :: {2, 3, 5, 6, 7, 23, 19, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse

6 | 5 | 6 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [5, 6] (inclusive)
6 | 5 | 7 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 8 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 9 :: {2, 3, 5, 6, 7, 19, 23, 2001, 5000, 96, 10, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 10 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- reversed [5, 10] (inclusive)
6 | 5 | 11 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 12 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 13 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 14 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 15 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 16 :: {2, 3, 5, 6, 7, 10, 96, 5000, 2001, 23, 19, 11, 32001, 79, 2012, 91, 77, 9, 47} <-- no reverse
6 | 5 | 17 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- reversed [5, 17] (inclusive)
6 | 5 | 18 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse

7 | 6 | 7 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 8 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 9 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 10 :: {2, 3, 5, 6, 7, 9, 77, 91, 2012, 79, 32001, 11, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 11 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- reversed [6, 11] (inclusive)
7 | 6 | 12 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 13 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 14 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 15 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 16 :: {2, 3, 5, 6, 7, 9, 11, 32001, 79, 2012, 91, 77, 19, 23, 2001, 5000, 96, 10, 47} <-- no reverse
7 | 6 | 17 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [6, 17] (inclusive)
7 | 6 | 18 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse

8 | 7 | 8 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 9 :: {2, 3, 5, 6, 7, 9, 10, 96, 5000, 2001, 23, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 10 :: {2, 3, 5, 6, 7, 9, 10, 23, 2001, 5000, 96, 19, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [7, 10] (inclusive)
8 | 7 | 11 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- reversed [7, 11] (inclusive)
8 | 7 | 12 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 13 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 14 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 15 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 16 :: {2, 3, 5, 6, 7, 9, 10, 19, 96, 5000, 2001, 23, 77, 91, 2012, 79, 32001, 11, 47} <-- no reverse
8 | 7 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 32001, 79, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- reversed [7, 17] (inclusive)
8 | 7 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 32001, 79, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse

9 | 8 | 9 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- reversed [8, 9] (inclusive)
9 | 8 | 10 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 79, 32001, 2012, 91, 77, 23, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 77, 91, 2012, 32001, 79, 23, 2001, 5000, 96, 19, 47} <-- reversed [8, 12] (inclusive)
9 | 8 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- reversed [8, 13] (inclusive)
9 | 8 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 23, 79, 32001, 2012, 91, 77, 2001, 5000, 96, 19, 47} <-- no reverse
9 | 8 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- reversed [8, 17] (inclusive)
9 | 8 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse

10 | 9 | 10 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 96, 5000, 2001, 77, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- reversed [9, 12] (inclusive)
10 | 9 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 23, 47} <-- no reverse
10 | 9 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- reversed [9, 17] (inclusive)
10 | 9 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse

11 | 10 | 11 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 79, 32001, 2012, 91, 96, 5000, 2001, 77, 47} <-- no reverse
11 | 10 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 77, 2001, 5000, 96, 91, 2012, 32001, 79, 47} <-- reversed [10, 17] (inclusive)
11 | 10 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- reversed [10, 18] (inclusive)

12 | 11 | 12 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 79, 32001, 2012, 91, 96, 5000, 2001, 77} <-- no reverse
12 | 11 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 2001, 5000, 96, 91, 2012, 32001, 79} <-- reversed [11, 18] (inclusive)

13 | 12 | 13 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 2001, 5000, 96, 91, 2012, 32001, 79} <-- no reverse
13 | 12 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 96, 5000, 2001, 91, 2012, 32001, 79} <-- reversed [12, 14] (inclusive)
13 | 12 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- reversed [12, 15] (inclusive)
13 | 12 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- no reverse
13 | 12 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 91, 2001, 5000, 96, 2012, 32001, 79} <-- no reverse
13 | 12 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 32001, 2012, 96, 5000, 2001, 91} <-- reversed [12, 18] (inclusive)

14 | 13 | 14 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 2012, 32001, 96, 5000, 2001, 91} <-- reversed [13, 14] (inclusive)
14 | 13 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- reversed [13, 15] (inclusive)
14 | 13 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- no reverse
14 | 13 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 96, 32001, 2012, 5000, 2001, 91} <-- no reverse
14 | 13 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- reversed [13, 18] (inclusive)

15 | 14 | 15 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 2001, 5000, 2012, 32001, 96} <-- no reverse
15 | 14 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 32001, 2012, 5000, 2001} <-- reversed [14, 18] (inclusive)

16 | 15 | 16 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2012, 32001, 5000, 2001} <-- reversed [15, 16] (inclusive)
16 | 15 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2012, 32001, 5000, 2001} <-- no reverse
16 | 15 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 5000, 32001, 2012} <-- reversed [15, 18] (inclusive)

17 | 16 | 17 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 5000, 32001, 2012} <-- no reverse
17 | 16 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 32001, 5000} <-- reversed [16, 18] (inclusive)

18 | 17 | 18 :: {2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 5000, 32001} <-- reversed [17, 18] (inclusive)

FINAL OUTPUT:
{2, 3, 5, 6, 7, 9, 10, 11, 19, 23, 47, 77, 79, 91, 96, 2001, 2012, 5000, 32001}

Array elements == 19
Total get operations == 233
Total reverse operations == 44
Total O(1) operations == 277
Total elements squared == 361
Total recursive invocations of sort == 18

---
Space for the algorithm (I think) is O(N) (one stack frame per element approximately)
Time for the algorithm is (I think) is O(N^2)