Abstract / Summary

Sort elements at even and odd positions separately while keeping their original index order.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 63% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided Solution class implements a method sortEvenOdd that rearranges the elements of an input list nums. Elements at even positions (0-based) are sorted in ascending order, while elements at odd positions are sorted in descending order. The method then produces a new sequence by alternating values from the two sorted subsequences. The implementation uses Python’s slicing, the built-in sorted function, and a generator to emit the result lazily.

Key Steps

Extracting and sorting the even-indexed elements

even = sorted(nums[::2])

The slice nums[::2] selects every element whose index is a multiple of two, i.e., the even-indexed positions. The sorted call returns a new list containing these values in non-decreasing order.

Extracting and sorting the odd-indexed elements in reverse order

odd = sorted(nums[1::2], reverse=True)

The slice nums[1::2] starts at index 1 and steps by two, capturing all odd-indexed elements. By passing reverse=True to sorted, the resulting list is ordered from largest to smallest.

Interleaving the two sorted sequences

for a, b in zip(even, odd):
    yield a
    yield b

The zip function pairs elements from even and odd up to the length of the shorter list. Inside the loop, each pair is emitted sequentially using yield, producing an alternating pattern of even-sorted and odd-sorted values.

Handling a trailing element when the input length is odd

if len(nums) & 1:
    yield even[-1]

The expression len(nums) & 1 evaluates to true when the original list has an odd number of elements. In that case, the even list contains one more element than odd. The final yield returns the last element of even, completing the interleaved output.

Edge Cases Addressed

When the input list contains a single element, the slice for odd indices yields an empty list, and the zip loop does not execute. The conditional check detects the odd length and yields the sole element from even, correctly returning the original value.

If the input list has no odd-indexed elements (for example, a list of length 2), the odd list contains exactly one element. The zip loop processes the single pair, and the conditional block does not trigger because the length is even. The output consists of the two sorted values interleaved as expected.

When all elements are identical, both even and odd become lists of the same repeated value. The interleaving logic still produces a correctly ordered sequence, and the final conditional yields the extra copy when needed.

Performance Optimizations

The implementation leverages Python’s highly optimized C-level sorting algorithm, which is faster than a manual sorting routine. By using slicing (nums[::2] and nums[1::2]) the code creates views of the original list without explicit loops, reducing overhead.

The use of a generator (yield) means that the result is produced lazily. No intermediate list that holds the fully interleaved sequence is allocated; values are generated on demand. This approach minimizes memory consumption, especially for large inputs, because only the two sorted subsequences and a few loop variables occupy space.

The zip function stops at the shorter of the two sorted lists, avoiding index checks inside the loop. This built-in iterator is implemented in C and provides efficient pairwise traversal.

The final conditional uses a bitwise AND (len(nums) & 1) to test odd length. This operation is a constant-time integer check and avoids the overhead of a modulo operation.

Overall, the method combines built-in operations that are tuned for speed and low memory usage, resulting in an implementation that is both concise and performant.

Imagine a line of toys sitting on a shelf. Some toys are in spots like one, three, or five, and others are in spots like two, four, or six. This code looks at all the toys in the even spots first and puts them in a special order, like lining them up from the smallest to the tallest. Then it looks at the toys in the odd spots and puts them in the opposite order, from the tallest to the smallest. After that, it picks up one toy from the even pile, then one from the odd pile, and keeps doing that to build a brand new line. If there is one leftover toy at the very end because the line started with an odd number of spots, it just adds that last one to the new line.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python			TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java		Python	Go		TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	everthis		JS
	fartem				Ruby
	fsq	C++
	halfrost						Go
	JoshCrozier		JS
	lkwq007					Python
	suxrobGM							C#
	varunu28			Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
fartem	Ruby
fsq	C++
halfrost	Go
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality