Complexity of a sortBy in Haskell

Question

I came up with an idea to solve another SO question and am hoping for some help with determining the function's complexity since I'm not too knowledgeable about that. Would I be correct in guessing that "unsorting" each of the chunks would be O (n * log 2) ? And then what would be the complexity of the sortBy function that compares the last of one chunk to the head of another? My guess is that that function would only compare pairs and not require finding one chunk's order in terms of the total list. Also, would Haskell offer different complexity because of a lazy optimization of the overall function? Thanks, in advance!

import Data.List.Split (chunksOf)
import Data.List (sortBy)

rearrange :: [Int] -> [Int]
rearrange = concat 
          . sortBy (\a b -> compare (last a) (head b)) 
          . map (sortBy (\a b -> compare b a)) 
          . chunksOf 2

Answer 1

Well step by step

1. chunksOf 2 must iterate through the whole list so O(n) and we half the length of the list. However, since constant multiples don't affect complexity we can ignore this.
2. map (sortBy... iterates through the whole list O(n) doing a constant time operation* O(1)=O(1*n) = O(n)
3. sortBy with a constant time comparison* is O( n * log n)
4. concat which is O(n)

So in total O(n + n + n log n + n) = O ((3 + log n) * n) = O(n log n)

*Since the lists are guarenteed to be of length 2 or less, we can say that operations like sorting and accessing the last element are O(2 * log 2) and O(2) respectively, which are both constant time, O(1)

Answer 2

Let's look at the parts in isolation (let n be the length of the list argument):

• chunksOf 2 is O(n), resulting in a list of length (n+1) `quot` 2.
• map (sortBy ...): Since all lists that are passed to sortBy ... have length <= 2, each of those sorts is O(1), and thus the entire map is O(n) again.
• sortBy (\a b -> compare (last a) (head b)): The comparison is always O(1), since the lists whose last element is taken are of bounded length (<= 2), thus the entire sortBy operation is O(n*log n)
• concat is O(n) again.

So overall, we have O(n*log n).

Note, however, that

cmp = \a b -> compare (last a) (head b)

is an inconsistent comparison, for two lists a and b (say [30,10] and [25,15]), you can have

cmp a b == cmp b a = LT

I'm not sure that your algorithm always works.

After looking at the implementation of sortBy and tracing the sort a bit in my head, I think that for the given purpose, it works (provided the list elements are distinct) and the inconsistent comparison does no harm. For some sorting algorithms, an inconsistent comparison might cause the sorting to loop, but for merge sort variants, that should not occur.