مرتب‌سازی شل
پیاده‌سازی

در این الگوریتم از روش مرتب‌سازی درجی استفاده می‌شود. به عبارتی ابتدا لیست را به چند دسته تقسیم می‌کند و هر کدام را جداگانه مرتب می‌کند. برای مثال اگر در ابتدا به ۳ دسته تقسیم کند، هر دسته را جداگانه به روش درجی که گفته شد، مرتب می‌کند. در هر مرحله، تعداد دسته‌ها نصف می‌شود (دسته‌ها بر اساس باقی‌مانده شان یا همان دسته‌های هم نهشتی). این عمل را ادامه می‌دهد تا سرانجام، تنها یک دسته شامل کل لیست داشته باشیم.
به عنوان مثال رشته f d a c b e را تحت این الگوریتم مرتب می‌کنیم.

کد:
F d a c b e: شروع
c b a f d e: مرحله اول
 a b c e d f: مرحله دوم
 a b c d e f: نتیجه
در مرحله اول داده‌های با فاصله ۳ از یکدیگر، مقایسه و مرتب شده، در مرحله دوم داده‌های با فاصله ۲ از یکدیگر، مقایسه و مرتب می‌شوند و در مرحله سوم داده‌ها با فاصله یک از یکدیگر مقایسه و مرتب می‌شوند.
منظور از فاصله سه این است که عنصر اول با عنصر چهارم(۳+۱)، عنصر دوم با عنصر پنجم(۵=۳+۲) و عنصر سوم با عنصر ششم(۶=۳+۳) مقایسه شده در جای مناسب خود قرار می‌گیرد.
برای انتخاب فاصله در اولین مرحله، تعداد عناصر لیست بر ۲ تقسیم می‌شود(n/۲) و فاصله بعدی نیز با تقسیم فاصله فعلی بر ۲ حاصل می‌گردد و الگوریتم تا زمانی ادامه پیدا می‌کند که این فاصله به صفر برسد. برای نمونه اگر تعداد عناصر برابر با ۱۰ باشد، فاصله در مرحله اول برابر با ۵، در مرحله دوم برابر با ۲ ور در مرحله سوم برابر با ۱ و در نهایت برابر با صفر خواهد بود.
حال به عنوان یک مثال عددی، مثال زیر را در نظر بگیرید:
فرض کنید لیستی مانند لیست روبرو داریم که می‌خواهیم با استفاده از این الگوریتم آن را مرتب کنیم : [ ۱۳ ۱۴ ۹۴ ۳۳ ۸۲ ۲۵ ۵۹ ۹۴ ۶۵ ۲۳ ۴۵ ۲۷ ۷۳ ۲۵ ۳۹ ۱۰ ]. حال اگر ما با یک گام (دسته‌بندی) ۵ تایی شروع کنیم، جدولی با ۵ ستون خواهیم داشت که صورت زیر خواهد بود:
۱۳ ۱۴ ۹۴ ۳۳ ۸۲
۲۵ ۵۹ ۹۴ ۶۵ ۲۳
۴۵ ۲۷ ۷۳ ۲۵ ۳۹
۱۰
حال اگر هر ستون را مرتب کنیم، خواهیم داشت:
۱۰ ۱۴ ۷۳ ۲۵ ۲۳
۱۳ ۲۷ ۹۴ ۳۳ ۳۹
۲۵ ۵۹ ۹۴ ۶۵ ۸۲
۴۵
برای اولین فراخوانی لیست رویرو را خواهیم داشت: [ ۱۰ ۱۴ ۷۳ ۲۵ ۲۳ ۱۳ ۲۷ ۹۴ ۳۳ ۳۹ ۲۵ ۵۹ ۹۴ ۶۵ ۸۲ ۴۵ ]. در اینجا عدد ۱۰ که در ابتدای لیست بود، به انتهای لیست آورده شده‌است. سپس لیست با استفاده از یک دسته بنده ۳ تایی و پس از آن یک دسته‌بندی ۱ تایی به‌وسیلهٔ مرتب‌سازی درجی مرتب خواهد شد.
پیاده‌سازی اصلی در بدترین حالت (O(n ۲ مقایسه و جابجایی انجام می‌دهد.
نوع دیگری از این الگوریتم با پیچیدگی کمتر نیز پیاده‌سازی شده که آن را به (O(n log۲ n ارتقا داده‌است ولی هنوز هم پیچیدگی این الگوریتم بدتر از بقیه مرتب‌سازی‌های مقایسه‌ای است که در (O(n log n عمل می‌کنند.

مرتب‌سازی شِل با مقایسهٔ عناصری که با یک فاصله (gap) از چندین مکان، جدا هستند مرتب‌سازی درجی را ارتقا می‌دهد.
این عمل باعث می‌شود که یک عنصر «قدم‌های بزرگ‌تری» به سمت مکان نهایی خود بردارد. گذرهای چند گانه روی اطلاعات با کوچک و کوچک‌تر کردن اندازه‌های فاصله‌ها انجام می‌شوند. آخرین مرحلهٔ مرتب شِل شامل یک مرتب‌سازی درجی ساده‌است ولی بعد از آن می‌توانیم مطمئن باشیم که آرایهٔ داده‌ها تقریباً مرتب شده‌است.
یک مقدار کوچک را که به‌طور اولیه در انتهای غلط آرایه قرار گرفته‌است را در نظر بگیرید.
با استفاده از یک مرتب‌سازی (O(n ۲ مثل مرتب‌سازی حبابی یا درجی، باید n مقایسه و جابجایی انجام دهیم تا این مقدار را روی کل آرایه تا انتهای دیگر آن جابجا کنیم. مرتب‌سازی شِل ابتدا مقادیر را با استفاده از قدم‌های بسیار بزرگ جابجا می‌کند، پس یک عنصر کوچک با چند مقایسه و جابجایی جزئی، مقدار زیادی از مسیر به سمت موقعیت نهایی خود را می‌پیماید.
عملکرد مرتب‌سازی شِل را می‌توان به این صورت تصور کرد: تغییر لیست به یک جدول و مرتب کردن ستون‌ها (با استفاده از مرتب‌سازی درجی)، تکرار مرحله قبل، هر دفعه با تعداد کمتری از ستون‌های دراز تر. در نهایت جدول فقط یک ستون خواهد داشت که همان لیست مرتب شده نهایی است.
تبدیل لیست به جدول برای راحت تر تصور کردن نحوه انجام مرتب‌سازی است در حالی که خود الگوریتم، مرتب‌سازی را درجا انجام می‌دهد (با افزایش ضریب با استفاده از اندازهٔ گام).

برای مثال لیستی از اعداد به صورت {۱۳, ۱۴, ۹۴, ۳۳, ۸۲, ۲۵, ۵۹, ۹۴, ۶۵, ۲۳, ۴۵, ۲۷, ۷۳, ۲۵, ۹۳, ۱۰}  را در نظر بگیرید. اگر اندازه قدم را ۵ در نظر بگیریم می‌توان این گونه تصور کرد که لیست را به یک جدول با ۵ ستون تبدیل کرده‌ایم؛ که به صورت زیر خواهد بود:
۱۳ ۱۴ ۹۴ ۳۳ ۸۲
۲۵ ۵۹ ۹۴ ۶۵ ۲۳
۴۵ ۲۷ ۷۳ ۲۵ ۳۹
۱۰
سپس هر ستون را مرتب می‌کنیم، که خواهیم داشت:
۱۰ ۱۴ ۷۳ ۲۵ ۲۳
۱۳ ۲۷ ۹۴ ۳۳ ۳۹
۲۵ ۵۹ ۹۴ ۶۵ ۸۲
۴۵
اگر این جدول را مثل لیستی از اعداد از انتها بخوانیم خواهیم داشت،  {۱۰, ۱۴, ۷۳, ۲۵, ۲۳, ۱۳, ۲۷, ۹۴, ۳۳, ۳۹, ۲۵, ۵۹, ۹۴, ۶۵, ۸۲, ۴۵}  که در آن عدد ۱۰ که در لیست اولیه در انتها قرار داشت به ابتدای لیست آمده‌است. این لیست دوباره با یک مرتب‌سازی سه فاصله‌ای و در نهایت یک مرتب‌سازی یک فاصله‌ای (مرتب‌سازی درجی ساده) مرتب خواهد شد.
ایده و طرز کار این الگوریتم به صورت زیر است:
چیدن دنباله داده‌ها در یک آرایه دو بعدی
مرتب‌سازی ستون‌های آرایه
با این کار، دنباله داده‌ها اندکی مرتب می‌شود و سپس عملیات بالا مجدداً تکرار می‌شود ولی این بار با آرایه‌ای کوچک‌تر. تا در نهایت در مرحله آخر به آرایه‌ای تنها با یک ستون می‌رسد.
به عنوان مثال برای مرتب‌سازی داده‌های { ۲ ۸ ۹ ۴ ۳ ۷ ۵ ۱ ۶ ۰ ۲ ۴ ۸ ۶ ۱ ۵ ۰ ۹ ۷ } با این روش، ابتدا داده‌ها در چند ستون (مثلاً در این جا در ۷ ستون) قرار داده می‌شود و سپس هر ستون به صورت مجزا مرتب می‌شود:
۳ ۷ ۹ ۰ ۵ ۱ ۶ ۳  ۳ ۲ ۰ ۵ ۱ ۵
۸ ۴ ۲ ۰ ۶ ۱ ۵ -> ۷  ۴ ۴ ۰ ۶ ۱ ۶
۷ ۳ ۴ ۹ ۸ ۲ ۸ ۷ ۹ ۹ ۸ ۲
در مرحله بعد:
۳ ۳ ۲ ۰ ۰ ۱
۰ ۵ ۱ ۱ ۲ ۲
۵ ۷ ۴ ۳ ۳ ۴
۴ ۰ ۶ -> ۴ ۵ ۶
۱ ۶ ۸ ۵ ۶ ۸
۷ ۹ ۹ ۷ ۷ ۹
۸ ۲  ۸ ۹