Haskell sort - odd and even sort

Haskell is a purely functional static and non-strict language, i.e., it does not evaluate expressions until needed. With its high degree of pattern matching, this combination allows greater control over complex problems and allows high-order functions to be a viable solution. However, Haskell is not a beginner-friendly language and has a steep learning curve. Moreover, its pure functionality requires extra effort while creating functions and working with the language.

The odd and even sort, also known as the brick sort, is a variation of the bubble sort algorithm. The odd-even sort is a simple algorithm that works by repetitively comparing and swapping (if need be) adjacent elements in a list until the entire list is sorted. The algorithm can be split into two parts: the odd pass and the even pass.

In the odd pass, elements at odd indices (i.e., 1, 3, 5, ... ) are compared with their immediate next odd element, i.e., the element at index 1 will compare itself to the element at index 3. If the current element, i.e., the element at index 1, is larger, it is swapped with the element at index 3. In this way, odd-indexed elements are swapped through a bubble sort variant. This same process is implemented for the even pass with even indices (i.e., 0, 2, 4, ...).

After the first traversal through both passes, the algorithm continues alternating between both passes until the entire list is sorted.

-- Swap elements at the given indices in a list
swap :: Int -> Int -> [a] -> [a]
swap i j xs = [if k == i then xs !! j 
                else if k == j then xs !! i 
                else xs !! k | k <- [0..length xs - 1]]
-- Perform a single pass of the odd-even sort algorithm
oddEvenPass :: (Ord a) => [a] -> [a]
oddEvenPass [] = []
oddEvenPass [x] = [x]
oddEvenPass (x1:x2:xs)
    | x1 > x2 = swap 0 1 (x1:x2:xs)
    | otherwise = x1 : oddEvenPass (x2:xs)
-- Perform the odd-even sort algorithm until no swaps are needed
oddEvenSort :: (Ord a) => [a] -> [a]
oddEvenSort xs
    | sorted = xs
    | otherwise = oddEvenSort sortedList
    where
        sortedList = oddEvenPass xs
        sorted = sortedList == xs
-- Execute example code 
main :: IO ()
main = do
    let unsortedList = [5, 2, 9, 1, 2, 6, 4]
    putStrLn "Unsorted list:"
    print unsortedList
    
    let sortedList = oddEvenSort unsortedList
    putStrLn "Sorted list:"
    print sortedList

We will now break down the code.

Lines 1–3: The swap function swaps two elements at indices i and j in the list. It does so by directly creating a new list by iterating through the indices of the input list and swapping the elements needed.
Lines 7–13: The oddEvenPass function ensures that it swaps elements at adjacent odd indices in each pass while keeping elements at adjacent even indices. This moves the larger elements to the end of the list (in ascending order).
Lines 16–22: The oddEvenSort function calls the oddEvenPass function repeatedly until the list is fully sorted and does not have more swaps.
Lines 23–33: The main function is the driver code for the program. It runs the functions created above and prints out its result.

The time complexity of this algorithm is $O(n)$ in its best case and $O(n^{2})$ in its worst case. In the best-case scenario, the input list is already sorted, and the algorithm only needs to run through it once to check its status. In the worst-case scenario, all iterations of both passes are subject to swapping to achieve the desired result.

This algorithm's space complexity is $O(1)$ because it performs in-place swaps, so it does not require additional data structures to store its interim values.

Haskell sort - odd and even sort

Logic

Code

Complexities

Conclusion