2
$\begingroup$

Why is this sort algorithm correct? Many thanks!

Task:

Suppose all elements in an array with length $n = 2^m$ are in descending order: $a_1 > a_2 > ... > a_n$, we need to turn them into ascending order.

Algorithm:

For each step from $1$ to $m$:

  1. Swap each adjacent (odd index, even index) pair into ascending order, so that: $a_1 \le a_2, a_3 \le a_4, ... , a_{n-1} \le a_n$
  2. Move all elements with odd index to the front of those with even index, so $a_1, a_2, a_3, a_4, ..., a_{n - 1}, a_n$ turns to : $a_1, a_3, ..., a_{n - 1}, a_2, a_4, ..., a_n$

Example:

Sort result after each step with $n = 8$:

[0] 8 7 6 5 4 3 2 1
[1] 7 5 3 1 8 6 4 2
[2] 5 1 6 2 7 3 8 4
[3] 1 2 3 4 5 6 7 8

Code:

#include <stdlib.h>

void swap(int *arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

void magic_sort(int *arr, int *result, int n)
{
    int half = n >> 1;
    int i;

    /* Swap adjacent (odd index, even index) pair into ascending order */
    for (i = 1; i <= n; i += 2)
    {
        if (arr[i] > arr[i + 1])swap(arr, i, i + 1);
    }

    /* Move all elements with odd index to front half */
    for (i = 1; i <= n; i += 2)
    {
        result[(i + 1) / 2] = arr[i];
    }

    /* Move all elements with even index to tail half */
    for (i = 2; i <= n; i += 2)
    {
        result[half + i / 2] = arr[i];
    }

    for (i = 1; i <= n; i++)
    {
        arr[i] = result[i];
    }
}

int main()
{
    int m = 3;
    int n = 1 << m;
    int *arr = (int *)malloc(sizeof(*arr) * (n + 1));
    int *result = (int *)malloc(sizeof(*arr) * (n + 1));
    int step, i;

    printf("[%d] ", 0);

    for (i = 1; i <= n; i++)
    {
        arr[i] = n + 1 - i;

        printf("%d ", arr[i]);
    }

    printf("\n");

    for (step = 0; step < m; step++)
    {
        magic_sort(arr, result, n);

        printf("[%d] ", step + 1);

        for (i = 1; i <= n; i++)
        {
            printf("%d ", arr[i]);
        }

        printf("\n");
    }

    free(arr);
    free(result);

    return 0;
}
$\endgroup$
1
$\begingroup$

This is an interesting algorithm.

Conventions

Array indexes start with 0. Note this convention is different from the convention used in the question. This convention helps us see what is going on more easily.

All arrays have length $n=2^m$ for some positive integer $m$.

Given any array $b_0, b_1, b_2, b_3,\cdots, b_{n - 2}, b_{n-1}$, the magic shuffle $M$ maps it to the array $b_1, b_3, \cdots, b_{n-1}, b_0, b_2, \cdots, b_{n-2}.$ Please note that I avoid using the term "sort" since this algorithm is hardly about sorting.

Let $A_0$ be the array $a_0, a_1, \cdots, a_{n-1}$ (that is, $A_0[i]=a_i$). Define $A_k$ recursively by $A_{k+1}= M(A_k)$.

Claim: $A_m$ is the reverse of $A_0$, which is $a_{n-1}, a_{n-2}, \cdots, a_0$.

Proof of the claim. For an array $B$, we can check by the definition of the magic shuffle, $$M(B)[i] = \begin{cases} B[2i+1] & \text{ if }i\lt 2^{m-1},\\ B[2(i-2^{m-1})]&\text{ if } i\ge 2^{m-1}.\end{cases}$$

For an integer $i=i_{m-1}2^{m-1} + i_{m-2}2^{m-2} + \cdots + i_12 + i_0$, where $i_t\in\{0,1\}$, let $(i_{m-1}i_{m-2}\cdots i_1i_0)_2$ be its representation in base 2. We can easily check that

$$M(B)[(i_{m-1}i_{m-2}i_{m-3}\cdots i_1i_0)_2] = B[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$ where $\overline{x}=1-x$ for $x=0,1$. So we have $$A_1[i] = M(A_0)[i] = A_0[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$ $$A_2[i] = M(A_1)[i] = A_1[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_{m-3}\cdots i_1i_0\overline{i_{m-1}}\overline{i_{m-2}})_2]$$ $$\cdots$$ $$A_{m-1}[i] = M(A_{m-2})[i] = A_{m-2}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_0\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1})_2]$$ $$A_m[i] = M(A_{m-1})[i] = A_{m-1}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1}\overline{i_0})_2]$$

Since $i + (\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_1}\overline{i_0})_2 = (\overline1\overline1\cdots\overline1\overline1)_2 = n-1$, we have proved the claim.

An exercise

Let $a_0, a_1, \cdots, a_{n-1}$ be an array of length $n=2^m$ for some positive integer $m$. For each step from 1 to m, repeat the following shuffle. For each term in the front half of the array, insert right before it the $n/2$-th term after it. Here is the result array after each shuffle for $n=16$.

[0]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16  
[1]  9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8  
[2] 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4  
[3] 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2  
[4] 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  

Show that we will obtain the initial array reversed in the end of $m$ shuffles.

If you consider the array as a deck of cards, then this shuffle is the (perfect) in (riffle) shuffle. In particular, if you repeat 10 in shuffles on a deck of 32 cards, you will end up with the deck of cards in its original order.

$\endgroup$
1
$\begingroup$

Notations

Array indexes start with 1 as in the question.

Fix some positive integer $m$ such that $n=2^m$.

Given any array $b_1, b_2,b_3,b_4\cdots, b_{n - 1}, b_n$, the magic shuffle $M$ rearrangement it to the array $b_2, b_4, \cdots, b_{n}, b_1, b_3, \cdots, b_{n-1}.$

Let $A_0$ be the initial array $a_1, a_2, \cdots, a_{n}$ (that is, $A_0[i]=a_i$). Define $A_k$ recursively by $A_{k+1}= M(A_k)$.

Let "%" be the modulus operator with positive divisor as defined in Python/Java/C/C++/C#.


Lemma: for an array $B$, $M(B)[i] = B[(2i)\%(n+1)]$

Proof: please verify by the definition of the magic shuffle.

Claim: $A_k[i]=A_0[(2^ki)\%(n+1)]$ for any nonnegative integer $k$.

Proof: the claim is obviously true for $k=0$. If the claim is true for $k$, then $$\begin{align} A_{k+1}[i]&=M(A_k)[i]=A_k[(2i)\%(n+1)]\\ &=A_0[(2^k(2i)\%(n+1))\%(n+1)]=A_0[(2^{k+1}i)\%(n+1)] \end{align}$$ Hence by mathematical induction on $k$, the claim is true.

Corallay: $A_m$ is $a_n, a_{n-1}, \cdots, a_1$, the reverse of $A_0$.

Proof: $A_m[i]=A_0[(2^mi)\%(n+1)]=A_0[((n+1 -1)i)\%(n+1)]=A_0[n+1-i]$.


An exercise

Can you generalize this phenomenon to $n=3^m, 4^m, 5^m,\cdots$?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.