Metode ini dimulai dengan menyortir pasang elemen jauh terpisah dari satu sama lain, maka semakin mengurangi kesenjangan antara elemen untuk dibandingkan. Dimulai dengan berjauhan elemen dapat memindahkan beberapa out-of-tempat elemen ke posisi lebih cepat dari pertukaran tetangga terdekat yang sederhana.
Donald Shell menerbitkan versi pertama semacam ini pada tahun 1959.
Waktu berjalan dari Shellsort sangat bergantung pada urutan kesenjangan yang digunakannya. Bagi banyak varian praktis, menentukan kompleksitas waktu mereka tetap merupakan masalah terbuka.DeskripsiShellsort adalah generalisasi dari insertion sort yang memungkinkan pertukaran item yang terpisah jauh.
Idenya adalah untuk mengatur daftar elemen sehingga, mulai di mana saja, mengingat setiap elemen hth memberikan daftar diurutkan. Daftar semacam dikatakan-h diurutkan. Dengan kata lain, hal itu dapat dianggap sebagai h disisipkan daftar, masing-masing individu diurutkan.
Dimulai dengan nilai-nilai besar h, penataan ulang ini memungkinkan elemen untuk memindahkan jarak jauh dalam daftar asli, mengurangi jumlah besar gangguan dengan cepat, dan meninggalkan sedikit pekerjaan untuk langkah-langkah h-jenis yang lebih kecil untuk melakukan.
Jika file yang kemudian k-diurutkan untuk suatu bilangan bulat k lebih kecil, maka file tersebut tetap-h diurutkan. Setelah ide ini untuk urutan penurunan nilai h berakhir pada 1 dijamin untuk meninggalkan daftar diurutkan pada akhirnya.
Contoh dijalankan dari Shellsort dengan kesenjangan 5, 3 dan 1 ditampilkan di bawah. Pertama lulus, 5-pemilahan, melakukan insertion sort pada subarrays terpisah (a1, a6, a11), (a2, a7, A12), (a3, a8), (a4, a9), (a5, a10).
Misalnya, mengubah subarray (a1, a6, a11) dari (62, 17, 25) ke (17, 25, 62). Lulus berikutnya, 3-pemilahan, melakukan insertion sort pada subarrays (a1, a4, a7, a10), (a2, a5, a8, a11), (a3, a6, a9, A12). Lulus terakhir, 1-penyortiran, adalah semacam penyisipan biasa dari seluruh array (a1, ..., A12).Sebagai contoh menggambarkan, para subarrays yang Shellsort beroperasi pada awalnya pendek; kemudian mereka lagi tapi hampir memerintahkan. Dalam kedua kasus insertion sort bekerja secara efisien.Shellsort tidak stabil: mungkin mengubah urutan relatif elemen dengan nilai-nilai yang sama. Ini adalah adaptif algoritma sorting dalam dijalankan lebih cepat ketika input sebagian diurutkan.PseudocodeMenggunakan urutan kesenjangan Marcin Ciura itu, dengan insertion sort batin.
# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]
# Start with the largest gap and work down to a gap of
1
foreach (gap in gaps)
{
# Do a gapped
insertion sort for this gap size.
# The
first gap elements a[0..gap-1] are already in gapped order
# keep
adding one more element until the entire array is gap sorted
for
(i = gap; i < n; i += 1)
{
# add
a[i] to the elements that have been gap sorted
#
save a[i] in temp and make a hole at position i
temp =
a[i]
#
shift earlier gap-sorted elements up until the correct location for a[i] is
found
for
(j = i; j >= gap and a[j - gap] > temp; j -= gap)
{
a[j]
= a[j - gap]
}
# put
temp (the original a[i]) in its correct location
a[j] =
temp
}