title: What is an appropriate sort algorithm for an embedded system?
body: <p>I'm developing the software for an embedded system, and I need to implement a sorting routine, and I'm having trouble choosing an optimal solution. My requirements are as follows:</p>
  
  <ol>
  <li>Because this is a very memory-limited system, space complexity is a primary factor.</li>
  <li>Because the number of elements to sort will generally be small, and the sorting will happen only occasionally, time complexity is not necessarily a primary factor.</li>
  <li>A stable algorithm is a requirement for my application.</li>
  <li>Because this is an embedded system, code size is a factor.</li>
  <li>There is no guarantee that the data will initially be in a nearly-sorted order.</li>
  </ol>
  
  <p>I've considered the following algorithms:</p>
  
  <ul>
  <li>bubble sort (yes, even though I'm ashamed to say it)</li>
  <li>gnome sort</li>
  <li>insertion sort</li>
  <li>in-place merge sort (though it seems to me that this is more ideal with linked lists than arrays?)</li>
  </ul>
  
  <p>While the answer (for my exact circumstances) may very well be, "uh, duh, it doesn't really matter, use bubble sort for all we care", that answer is not very useful. <strong>In general, what sort algorithms are useful on embedded systems?</strong></p>