מיון סלים – הבדלי גרסאות

עבור חלוקה של n איברים לתוך m סלים, בהנחה שהפונקציה המחלקת לוקחת <math>\ O(1)</math> לכל איבר אזי פעולת החלוקה לוקחת <math>\ O(N)</math> זמן, במקרה הגרוע, אם פיזור האיברים אינו אחיד, לסל אחד נכנסו <math>\ O(N)</math> איברים ומיונם ייקח <math>\ O(NlogN)</math> והמעבר על שאר הסלים לוקח <math>\ O(M)</math> זמן, וסה"כ לוקח <math>\ O(NlogN+M)</math>, לעומת זאת, בהנחה שאכן הפיזור אחיד, צריך למיין m תאים שבכל אחד מהם <math>\ O(N/M)</math> איברים שלמיין כל אחד מהם לוקח <math>\ O((N/M)log(N/M))</math>,וסה"כ אחרי שמכפילים ב m תאים ומוסיפים את הסיבוכיות של החלוקה לתאים, צריך גם לקחת בחשבון גם מקרה שm הרבה יותר גדולה בסדר גודל מ<math>\ N</math> ולוקח יותר זמן המעבר על התאים ולכן צריך לחבר לסיבוכיות <math>\ M</math>, זה לוקח <math>\ O(Nlog(N/M)+M)</math>, במקרה האידיאלי, שבו <math>\ M</math>= <math>\Theta\left(N\right)</math> וההתפלגות אחידה הסיבוכיות היא בתוחלת<math>\ O(N)</math>.