codelessgenie blog

Sort Even and Odd Placed Elements in Increasing Order

Sorting is a fundamental operation in computer science. In this blog, we'll explore a specific sorting problem: sorting the elements at even and odd positions in a list (or array) independently in increasing order. This can be useful in various scenarios where we want to manipulate data based on its position in a sequence.

2026-06

Table of Contents#

  1. Problem Statement
  2. Approach
  3. Implementation in Python
  4. Common Practices and Best Practices
  5. Example Usage
  6. Complexity Analysis
  7. References

1. Problem Statement#

Given an array (or list) of integers, we need to sort the elements at even indices (0-based indexing) in increasing order and also sort the elements at odd indices in increasing order. The indices are considered separately for this sorting.

2. Approach#

  • Separate the Elements: First, we create two separate lists. One list will hold all the elements at even indices, and the other will hold all the elements at odd indices.
  • Sort Each List: Then, we sort each of these two lists independently in increasing order.
  • Reconstruct the Result: Finally, we reconstruct the original array (or list) by placing the sorted elements from the even - index list back at the even indices and the sorted elements from the odd - index list back at the odd indices.

3. Implementation in Python#

def sort_even_odd(arr):
    even_list = []
    odd_list = []
    for i in range(len(arr)):
        if i % 2 == 0:
            even_list.append(arr[i])
        else:
            odd_list.append(arr[i])
    even_list.sort()
    odd_list.sort()
    result = []
    even_index = 0
    odd_index = 0
    for i in range(len(arr)):
        if i % 2 == 0:
            result.append(even_list[even_index])
            even_index += 1
        else:
            result.append(odd_list[odd_index])
            odd_index += 1
    return result

4. Common Practices and Best Practices#

  • Input Validation: In a more robust implementation, we should add input validation. For example, check if the input is actually a list (or array) and not some other data type. In Python, we can use isinstance(arr, list) to check if arr is a list.
  • Memory Management: If the input list is very large, creating two separate lists (even_list and odd_list) can consume a significant amount of memory. In such cases, we can consider in-place sorting techniques with more complex logic, but for simplicity and readability, the above approach is often preferred for small to medium-sized lists.
  • Code Readability: Using descriptive variable names (like even_list and odd_list) improves the readability of the code. Also, adding comments to explain the key steps (like separating elements, sorting, and reconstructing) can make the code more understandable for other developers (or for yourself when you revisit the code later).

5. Example Usage#

arr = [1, 2, 3, 4, 5, 6]
print(sort_even_odd(arr))
# Output: [1, 2, 3, 4, 5, 6] (already sorted in a way that even and odd placed elements are sorted)
 
arr = [5, 3, 2, 8, 1, 4]
print(sort_even_odd(arr))
# Output: [1, 3, 2, 4, 5, 8]

6. Complexity Analysis#

  • Time Complexity:
    • Separating Elements: This step takes $O(n)$ time, where $n$ is the length of the input list, as we are iterating through each element once.
    • Sorting: Sorting each of the two lists (even_list and odd_list) takes $O(k\log k)$ and $O(m\log m)$ time respectively, where $k$ is the number of elements in the even_list and $m$ is the number of elements in the odd_list. In the worst case, $k + m=n$, and if $k = m=\frac{n}{2}$, then the total sorting time is $O(n\log n)$ (since $\frac{n}{2}\log\frac{n}{2}+\frac{n}{2}\log\frac{n}{2}=n\log\frac{n}{2}\approx n\log n$ for large $n$).
    • Reconstructing the Result: This step also takes $O(n)$ time.
    • Overall, the time complexity is $O(n\log n)$ due to the sorting steps.
  • Space Complexity:
    • We are creating two additional lists (even_list and odd_list). In the worst case, each of these lists can have $\frac{n}{2}$ elements. So, the space complexity is $O(n)$.

7. References#