I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. What algorithm is the most power efficient algorithm for sorting arbitrary text strings?

  • 2
    $\begingroup$ I suspect that depends heavily on your architecture. Do you know what operations are most/least expensive for ARM? $\endgroup$ – jmite Jul 31 '13 at 22:30
  • 4
    $\begingroup$ Also, are you sorting large quantities of data? Do you have any evidence to suggest that sorting is the power-bottleneck in your app? Always profile before you optimize. $\endgroup$ – jmite Jul 31 '13 at 22:31
  • $\begingroup$ Well then it could even depend on the exact ARM chip so I probably need a more generic answer? $\endgroup$ – JoshuaCC Jul 31 '13 at 22:32
  • 1
    $\begingroup$ By the way, the sentence "I will implement it in C for extra power efficiency." rings several alarm bells. Are you such a good C programmer that you are sure to make a better job than several decades of library development? $\endgroup$ – Raphael Aug 1 '13 at 13:17
  • 5
    $\begingroup$ OK, I'll say something that should have been said already: please, please, for the sake of whatever deities you pray to, please, do not choose a sorting algorithm at this stage based on its energy efficiency. Write your entire end-to-end application using the most standard method first, and only then should you possibly consider changing the sorting algorithm if during performance testing you detect a measurable inefficiency. This stands naked on the roof and screams "premature optimization". $\endgroup$ – Patrick87 Aug 1 '13 at 14:45

As concluded by this paper, the algorithm with the better asymptotic run time seems to also have the better energy efficiency, which corroborates the assumption that an algorithm with a higher performance also has a higher energy efficiency.

  • $\begingroup$ Not true, at least generally. 1) As far as I can tell from skimming it, the paper does not consider the effect instrumentation may have. 2) "Better asymptotic runtime" is not the same as "better $O$-class". If one compares $O(n \log n)$ sorting algorithms, things become more interesing (see my answer). $\endgroup$ – Raphael Aug 1 '13 at 12:57

Smaller runtime is not all. In Evaluating Algorithms according to their Energy Consumption (Computability in Europe, 2009), Fudeus née Bayer and Nebel show that an algorithm with more executed instructions (this is typically analysed, at least in theory) might use less energy¹.

Keep in mind that energy consumption is determined by at least

  • the algorithm itself,
  • the compiler,
  • the CPU and
  • the hardware memory management.

One particular effect is that the energy consumption of modern CPUs is not just the sum of fixed contributions of all statements. The sequence is relevant, that is an addition may have different cost depending on whether it is executed after a jump or a subtraction. Hence, for example

  • instruction reordering by the compiler can have effects in all directions on energy consumption, depending on the target system, and
  • fewer operations cost more because e.g. the ALU is shut down in between operations and is costly to start up again.

  1. It might also be faster, mind.
  • 3
    $\begingroup$ Cache friendliness is a huge consideration. Not only does accessing more distant parts of the memory hierarchy use more energy but some energy is consumed by the system even when just waiting for a memory access to complete. By the way, more executed instructions is not the same as longer runtime; e.g., branch mispredictions, lack of ILP, and cache misses can make a shorter execution trace take longer to execute. Given static power consumption in non-sleep state, faster is often more energy efficient. $\endgroup$ – Paul A. Clayton Aug 1 '13 at 14:47
  • $\begingroup$ @PaulA.Clayton All true. FWIW, Fudeus and Nebel investigate "true" runtime and the "paradox" still occurs. $\endgroup$ – Raphael Aug 1 '13 at 14:55

The sort benchmark website has a category on energy efficient sorting. Currently, NTOSort and Tritonsort seem to be the best.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.