مثال دفترچه تلفن
اگر دفترچه تلفن بصورت تصادفي پر شده بود ما احتمالا هيچ وقت از آن استفاده نمي کرديم.
فرض کنيم ديدن هر رديف ½ ثانيه طول بکشد.
در ايلام حدودا 70000 خانه وجود دارد.
در بدترين حالت 35000 ثانيه يا 10 ساعت طول مي کشد تا شماره شخص مورد نظر را پيدا کنيد.
در يهترين حالت ½ ثانيه طول مي کشد تا شماره شخص مورد نظر پيدا شود.
بطور متوسط 5 ساعت طول مي کشد تا شماره شخص مورد نظر پيدا شود.
اما دفترچه تلفن مرتب شده است:
ما ابتدا به سراغ حرف اول اسم شخص مورد نظر مي رويم.
سپس دنبال صفحه اي مي رويم که با دو حرف اول اسم مورد نظر مطابقت دارد.
اگر به اندازه کافي به صفحه مورد نظر نزديک نباشيم، چند صفحه را با هم ورق مي زنيم.
الگوريتم مرتب سازي مجموعه اي از داده هاي aj که به صورت تصادفي مرتب شده اند را مي گيرد و آنها را طوري مرتب مي کند که براي تمام j ها (j>=0 و j<n ) و رابطه ترتيبي R :
a0 R a1 R a2 R … aj … R aN-1 R aN
اگر R برابر <= باشد، داده ها به صورت صعودي مرتب خواهند شد و هر عنصر از عنصر قبلي بزرگتر خواهد بود.
اگر R برابر >= باشد، داده ها به صورت نزولي مرتب خواهند شد و هر عنصر از عنصر قبلي کوچکتر خواهد بود.