Data Modelling & AI Data Structure & Algorithm

Sort Array such that smallest is at 0th index and next smallest it at last index and so on

23 June 2025

2

Given an array, arr[] of N integers, the task is to rearrange the array elements such that the smallest element is at the 0th position, the second smallest element is at the (N-1)th position, the third smallest element at 1st position, 4th smallest element is at the (N-2)th position, and so on for all integers in arr[].

Examples:

Input: arr[] = {10, 23, 12, 17, 9}
Output: 9 12 23 17 10
Explanation:
The smallest element is 9 which is put in the index 0.
Then the second smallest element is 10 which is put in the last position.
The third smallest element is put in the second position from the start.
The fourth smallest in the second position from the last and so on.
Input: arr[] = {1, 3, 3, 4, 5}
Output: 1 3 5 4 3

Approach: We will be using the Two Pointer Technique. The idea is to iterate from the start marked by variable i to the end marked by variable j of the array alternatively until they meet in the middle and keep updating the minimum values at these indices. Below are the steps:

Set the element at index i as the minimum value. Iterate over [i, j] and compare each value in this range with arr[i], and if the value in the range is less than arr[i] then swap the value between arr[i] and the current element. Increment the value of i.
Set the element at index j as the minimum value. Iterate over [i, j] and compare each value in this range with arr[j], and if the value in the range is less than arr[j] then swap the value between arr[j] and the current element. Decrement the value of j.
Place the smallest element in the i^th position at the first iteration and the next smallest element in the j^th position. Do this until both i and j point to the same position.

Below is the implementation of the above approach:

C++

// C++ program for the above approach 
#include <bits/stdc++.h>
using namespace std;
 
// Function to perform the rearrangement 
void rearrange(int a[], int N) 
{ 
     
    // Initialize variables 
    int i = 0, j = N - 1; 
    int min = 0, k, x = 0, temp; 
 
    // Loop until i crosses j 
    while (i < j) 
    { 
 
        // This check is to find the 
        // minimum values in the 
        // ascending order 
        for(k = i; k <= j; k++) 
        { 
            if (a[k] < a[min]) 
                min = k; 
        } 
 
        // Condition to alternatively 
        // iterate variable i and j 
        if (x % 2 == 0)
        { 
 
            // Perform swap operation 
            temp = a[i]; 
            a[i] = a[min]; 
            a[min] = temp; 
 
            // Increment i 
            i++; 
 
            // Assign the value of min 
            min = i; 
        } 
        else
        { 
 
            // Perform swap 
            temp = a[j]; 
            a[j] = a[min]; 
            a[min] = temp; 
 
            // Decrement i 
            j--; 
 
            // Assign the value of min 
            min = j; 
        } 
        x++; 
    } 
 
    // Print the array 
    for(i = 0; i < N; i++) 
        cout << a[i] << " "; 
}
 
// Driver Code
int main()
{
     
    // Given Array arr[] 
    int arr[] = { 1, 3, 3, 4, 5 }; 
     
    int N = sizeof(arr) / sizeof(arr[0]);
     
    // Function call 
    rearrange(arr, N);
 
    return 0;
}
 
// This code is contributed by divyeshrabadiya07

Java

// Java program for the above approach 
import java.io.*; 
import java.util.*; 
 
public class GFG { 
 
    // Function to perform the rearrangement 
    static void rearrange(int[] a) 
    { 
        // Initialize variables 
        int i = 0, j = a.length - 1; 
        int min = 0, k, x = 0, temp; 
 
        // Loop until i crosses j 
        while (i < j) { 
 
            // This check is to find the 
            // minimum values in the 
            // ascending order 
 
            for (k = i; k <= j; k++) { 
                if (a[k] < a[min]) 
                    min = k; 
            } 
 
            // Condition to alternatively 
            // iterate variable i and j 
            if (x % 2 == 0) { 
 
                // Perform swap operation 
                temp = a[i]; 
                a[i] = a[min]; 
                a[min] = temp; 
 
                // Increment i 
                i++; 
 
                // Assign the value of min 
                min = i; 
            } 
            else { 
 
                // Perform swap 
                temp = a[j]; 
                a[j] = a[min]; 
                a[min] = temp; 
 
                // Decrement i 
                j--; 
 
                // Assign the value of min 
                min = j; 
            } 
            x++; 
        } 
 
        // Print the array 
        for (i = 0; i < a.length; i++) 
            System.out.print(a[i] + " "); 
    } 
 
    // Driver Code 
    public static void main(String[] args) 
    { 
        // Given Array arr[] 
        int arr[] = { 1, 3, 3, 4, 5 }; 
 
        // Function Call 
        rearrange(arr); 
    } 
}

Python3

# Python3 program for 
# the above approach 
# Function to perform 
# the rearrangement 
def rearrange(a, N):
 
    # Initialize variables 
    i = 0
    j = N - 1
    min = 0
    x = 0
 
    # Loop until i crosses j 
    while (i < j):
     
        # This check is to find the 
        # minimum values in the 
        # ascending order 
        for k in range (i, j + 1):
            if (a[k] < a[min]):
                min = k
 
        # Condition to alternatively 
        # iterate variable i and j 
        if (x % 2 == 0):
         
            # Perform swap operation 
            temp = a[i]
            a[i] = a[min]
            a[min] = temp
 
            # Increment i 
            i += 1
 
            # Assign the value of min 
            min = i
         
        else:
         
            # Perform swap 
            temp = a[j]
            a[j] = a[min]
            a[min] = temp
 
            # Decrement i 
            j -= 1
 
            # Assign the value of min 
            min = j
         
        x += 1
     
    # Print the array 
    for i in range (N):
        print (a[i] ,end = " ")
 
# Driver Code
if __name__ == "__main__":
   
    # Given Array arr[] 
    arr = [1, 3, 3, 4, 5] 
     
    N = len(arr)
     
    # Function call 
    rearrange(arr, N)
     
# This code is contributed by Chitranayal

C#

// C# program for the above approach
using System;
 
class GFG{
 
// Function to perform the rearrangement
static void rearrange(int[] a)
{
     
    // Initialize variables
    int i = 0, j = a.Length - 1;
    int min = 0, k, x = 0, temp;
 
    // Loop until i crosses j
    while (i < j)
    {
         
        // This check is to find the
        // minimum values in the
        // ascending order
 
        for(k = i; k <= j; k++)
        {
            if (a[k] < a[min])
                min = k;
        }
 
        // Condition to alternatively
        // iterate variable i and j
        if (x % 2 == 0) 
        {
             
            // Perform swap operation
            temp = a[i];
            a[i] = a[min];
            a[min] = temp;
 
            // Increment i
            i++;
 
            // Assign the value of min
            min = i;
        }
        else
        {
             
            // Perform swap
            temp = a[j];
            a[j] = a[min];
            a[min] = temp;
 
            // Decrement i
            j--;
 
            // Assign the value of min
            min = j;
        }
        x++;
    }
     
    // Print the array
    for(i = 0; i < a.Length; i++)
        Console.Write(a[i] + " ");
}
 
// Driver Code
public static void Main(string[] args)
{
     
    // Given array arr[]
    int []arr = { 1, 3, 3, 4, 5 };
 
    // Function call
    rearrange(arr);
}
}
 
// This code is contributed by rutvik_56

Javascript

<script>
// javascript program for the above approach 
 
 
    // Function to perform the rearrangement
    function rearrange(a) {
        // Initialize variables
        var i = 0, j = a.length - 1;
        var min = 0, k, x = 0, temp;
 
        // Loop until i crosses j
        while (i < j) {
 
            // This check is to find the
            // minimum values in the
            // ascending order
 
            for (k = i; k <= j; k++) {
                if (a[k] < a[min])
                    min = k;
            }
 
            // Condition to alternatively
            // iterate variable i and j
            if (x % 2 == 0) {
 
                // Perform swap operation
                temp = a[i];
                a[i] = a[min];
                a[min] = temp;
 
                // Increment i
                i++;
 
                // Assign the value of min
                min = i;
            } else {
 
                // Perform swap
                temp = a[j];
                a[j] = a[min];
                a[min] = temp;
 
                // Decrement i
                j--;
 
                // Assign the value of min
                min = j;
            }
            x++;
        }
 
        // Print the array
        for (i = 0; i < a.length; i++)
            document.write(a[i] + " ");
    }
 
    // Driver Code
     
        // Given Array arr
        var arr = [ 1, 3, 3, 4, 5 ];
 
        // Function Call
        rearrange(arr);
 
// This code is contributed by todaysgaurav
</script>

Output

1 3 5 4 3

Time Complexity: O(N²) since two nested loops are used the time taken by the algorithm to complete all operations is quadratic.
Auxiliary Space: O(1) since no extra array is used so the space taken by the algorithm is constant

Efficient Approach

First sort the array and then using two pointers we will assign value as required by the question in the newArr array and then assign this newArr array value to the original array.

As mentioned in the question the first element of the new array is the smallest element in the 0th position, so newArr[0] = arr[0] as arr is already sorted, then the second smallest element to (n-1)th position means newArr[n-1] = arr[1], then newArr[1] = arr[2], newArr[n-2] = arr[3], so for this, we use two variable, where small pointing 0th position of newArr and large pointing (n-1)th position of newArr. on every fill-up of value in newArr, we increase small by 1 and decrease large by 1. so this way we achieve newArr as required in the question.

Step-by-step approach:

1. Sort given array arr
2. create n size newArr array
3. small = 0, large = 0
4. iterate from i = 0 to n-1
        if(i%2 == 0)
            newArr[small] = arr[i]
            small++
        else
            newArr[large] = arr[i]
            large--
5. copy all element from newArr to arr

Below is the implementation of the above approach:

C++

#include<bits/stdc++.h>
using namespace std;
 
void rearrangeArray(int arr[], int n) {
    // Sort the array
    sort(arr, arr + n);
 
    int newArr[n]; // Temporary array to store rearranged array
 
    int small = 0, large = n - 1;
 
    // Traverse the sorted array and rearrange elements
    for (int i = 0; i < n; i++) {
        // If i is even, pick smallest element
        if (i % 2 == 0) {
            newArr[small] = arr[i];
            small++;
        }
        // If i is odd, pick largest element
        else {
            newArr[large] = arr[i];
            large--;
        }
    }
 
    // Copy rearranged array to original array
    for (int i = 0; i < n; i++) {
        arr[i] = newArr[i];
    }
}
 
int main() {
    int arr[] = { 1, 3, 3, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
 
    rearrangeArray(arr, n);
 
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
 
    return 0;
}

Java

import java.util.Arrays;
 
public class GFG {
 
    // Function to rearrange the array alternatively
    static void rearrangeArray(int[] arr, int n) {
        // Sort the array
        Arrays.sort(arr);
 
        int[] newArr = new int[n]; // Temporary array to store rearranged array
 
        int small = 0, large = n - 1;
 
        // Traverse the sorted array and rearrange elements
        for (int i = 0; i < n; i++) {
            // If i is even, pick the smallest element
            if (i % 2 == 0) {
                newArr[small] = arr[i];
                small++;
            }
            // If i is odd, pick the largest element
            else {
                newArr[large] = arr[i];
                large--;
            }
        }
 
        // Copy rearranged array to the original array
        for (int i = 0; i < n; i++) {
            arr[i] = newArr[i];
        }
    }
 
    public static void main(String[] args) {
        int[] arr = {1, 3, 3, 4, 5};
        int n = arr.length;
 
        rearrangeArray(arr, n);
 
        // Print the rearranged array
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
}

Python3

def rearrange_array(arr):
    # Sort the array
    arr.sort()
 
    n = len(arr)
    new_arr = [0] * n # Temporary array to store rearranged array
 
    small = 0
    large = n - 1
 
    # Traverse the sorted array and rearrange elements
    for i in range(n):
        # If i is even, pick smallest element
        if i % 2 == 0:
            new_arr[small] = arr[i]
            small += 1
        # If i is odd, pick largest element
        else:
            new_arr[large] = arr[i]
            large -= 1
 
    # Copy rearranged array to original array
    for i in range(n):
        arr[i] = new_arr[i]
    return arr
 
arr = [1, 3, 3, 4, 5]
rearranged_arr = rearrange_array(arr)
print(rearranged_arr)

C#

using System;
 
class Program {
    static void rearrangeArray(int[] arr, int n)
    {
        // Sort the array
        Array.Sort(arr);
 
        int[] newArr = new int[n]; // Temporary array to
                                   // store rearranged array
 
        int small = 0, large = n - 1;
 
        // Traverse the sorted array and rearrange elements
        for (int i = 0; i < n; i++) {
            // If i is even, pick the smallest element
            if (i % 2 == 0) {
                newArr[small] = arr[i];
                small++;
            }
            // If i is odd, pick the largest element
            else {
                newArr[large] = arr[i];
                large--;
            }
        }
 
        // Copy rearranged array to the original array
        for (int i = 0; i < n; i++) {
            arr[i] = newArr[i];
        }
    }
 
    static void Main()
    {
        int[] arr = { 1, 3, 3, 4, 5 };
        int n = arr.Length;
 
        rearrangeArray(arr, n);
 
        for (int i = 0; i < n; i++) {
            Console.Write(arr[i] + " ");
        }
        Console.WriteLine();
    }
}

Javascript

function rearrangeArray(arr) {
    // Step 1: Sort the input array in ascending order
    arr.sort((a, b) => a - b);
 
    // Step 2: Create a new array to hold the rearranged elements
    const newArr = new Array(arr.length);
    let small = 0, large = arr.length - 1;
 
    // Step 3: Iterate through the sorted array and rearrange elements
    for (let i = 0; i < arr.length; i++) {
        // If the current index is even, place the smallest remaining element in newArr
        if (i % 2 === 0) {
            newArr[small] = arr[i];
            small++;
        }
        // If the current index is odd, place the largest remaining element in newArr
        else {
            newArr[large] = arr[i];
            large--;
        }
    }
 
    // Step 4: Copy the rearranged elements back to the original array
    for (let i = 0; i < arr.length; i++) {
        arr[i] = newArr[i];
    }
}
 
const arr = [1, 3, 3, 4, 5];
rearrangeArray(arr);
 
// Step 5: Print the rearranged array elements
console.log(arr.join(" "));

Output

1 3 5 4 3

Time Complexity: O(N*log(N)) sort operation take nlog(n) time.
Auxiliary Space: O(N) since we use extra temp array

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!

Sort Array such that smallest is at 0th index and next smallest it at last index and so on

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Nano Banana + Milvus: Turning Hype into Enterprise-Ready Multimodal RAG

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

LEAVE A REPLY Cancel reply

Most Popular

Honor Magic V5 review: How this temptingly thin foldable won me over

6 hours in, I’m already very impressed by Hollow Knight: Silksong

I’ve been on Spotify since day one and these are the 10 tricks worth knowing

Here’s another good look at Samsung’s first trifold phone

EDITOR PICKS

Honor Magic V5 review: How this temptingly thin foldable won me over

6 hours in, I’m already very impressed by Hollow Knight: Silksong

I’ve been on Spotify since day one and these are the 10 tricks worth knowing

POPULAR POSTS

Honor Magic V5 review: How this temptingly thin foldable won me over

6 hours in, I’m already very impressed by Hollow Knight: Silksong

I’ve been on Spotify since day one and these are the 10 tricks worth knowing

POPULAR CATEGORY

ABOUT US

FOLLOW US