മെർജ് സോർട്ട്

വിക്കിപീഡിയ, ഒരു സ്വതന്ത്ര വിജ്ഞാനകോശം.
മെർജ് സോർട്ട്
മെർജ് സോർട്ട് ഉപയോഗിച്ച് ഒരു അറേ സോർട്ട് ചെയ്യുന്നു
മെർജ് സോർട്ട് ഉപയോഗിച്ച് ഒരു അറേ സോർട്ട് ചെയ്യുന്നു
കുടുംബം സോർട്ടിങ്ങ് അൽഗൊരിതം
ഡാറ്റാ സ്ട്രക്‌ചർ അറേ
മോശം സമയസങ്കീർണ്ണത \Theta(N\;\log\;N)
നല്ല സമയസങ്കീർണ്ണത \Theta(N\;\log\;N)
ശരാശരി സമയസങ്കീർണ്ണത \Theta(N\;\log\;N)
മോശം മെമ്മറി സങ്കീർണ്ണത \Theta(N)
Optimal ചിലപ്പോൾ


ലളിതവും അതേ സമയം സമയസങ്കീർണ്ണത കുറഞ്ഞതുമായ ഒരു സോർട്ടിങ്ങ് അൽഗൊരിതമാണ്‌ മെർജ് സോർട്ട്. ഇത് ഒരു താരതമ്യ സോർട്ട് ആണ്‌. വിഭജിച്ച് കീഴടക്കുക (Divide and conquer) എന്ന രീതിയുപയോഗിക്കുന്ന അൽഗൊരിതങ്ങൾക്ക് ഉത്തമോദാഹരണമായ മെർജ് സോർട്ട് സാധാരണ രീതിയിൽ സ്റ്റേബിൾ ആണ്‌. 1945-ൽ ജോൺ വോൺ ന്യൂമാനാണ്‌ ഈ അൽഗൊരിതം കണ്ടുപിടിച്ചത്.

അൽഗൊരിതം[തിരുത്തുക]

മെർജ് സോർട്ടിന്റെ അൽഗൊരിതത്തിലെ പ്രധാന പടികൾ ഇവയാണ്‌:

  1. അറേയുടെ വലിപ്പം 0 അഥവാ 1 ആണെങ്കിൽ അറേ സോർട്ട് ചെയ്യേണ്ട ആവശ്യമില്ല
  2. അറേയിൽ രണ്ടോ അതിലധികമോ അംഗങ്ങളുണ്ടെങ്കിൽ അതിനെ ഏകദേശം തുല്യനീളമുള്ള രണ്ട് അറേകളായി വിഭജിക്കുക
  3. ഇങ്ങനെ ലഭിച്ച ഓരോ അറേയിലും സംഖ്യകൾ ക്രമത്തിലാക്കാൻ മെർജ് സോർട്ട് ചെയ്യുക
  4. സംഖ്യകൾ ക്രമത്തിലായ ഈ രണ്ട് അറേകളെ ക്രമം തെറ്റാത്ത രീതിയിൽ യോജിപ്പിക്കുക

ഇങ്ങനെ റികർഷൻ ഉപയോഗിച്ചാണ്‌ അൽഗൊരിതം വിശദീകരിച്ചിരിക്കുന്നതെങ്കിലും ചെറിയ മാറ്റത്തോടെ റികർഷൻ ഇല്ലാതെയും മെർജ് സോർട്ട് ചെയ്യാനാവും.

താരതമ്യം[തിരുത്തുക]

ഹീപ് സോർട്ടിന്റെയും മെർജ് സോർട്ടിന്റെയും സമയസങ്കീർണ്ണതകൾ തുല്യമാണെങ്കിലും ഹീപ് സോർട്ടിന്‌ മെർജ് സോർട്ടിനെക്കാൾ താഴെപ്പറയുന്ന മെച്ചങ്ങളുണ്ട് :

  • അറേക്ക് പുറമെ O(1) മെമ്മറി മാത്രമേ ഹീപ് സോർട്ടിന്‌ ആവശ്യമുള്ളൂ. എന്നാൽ മെർജ് സോർട്ടിന്‌ O(N) ആവശ്യമാണ്‌
  • സാധാരണ രീതിയിൽ ഹീപ് സോർട്ട് മെർജ് സോർട്ടിനെക്കാൾ വേഗത്തിൽ സംഖ്യകളെ ക്രമീകരിക്കും

ക്വിക്ക് സോർട്ട് ആണ്‌ വേഗതയ്ക്ക് വേണ്ടി സാധാരണ ഉപയോഗിക്കപ്പെടാറ്.

എങ്കിലും മെർജ് സോർട്ട് ചില കാര്യങ്ങളിൽ ഇവയെക്കാൾ മികച്ചു നിൽക്കുന്നു :

  • ഇത് ഒരു സ്റ്റേബിൾ സോർട്ട് ആണ്‌
  • ഒന്നിലധികം പ്രോസസ്സറുകൾ ഉപയോഗിച്ച് സമാന്തരമായി മെർജ് സോർട്ട് ചെയ്യാനാകും
  • ലിങ്ക്ഡ് ലിസ്റ്റുകളിൽ ലിസ്റ്റിന്‌ പുറമെ O(1) മെമ്മറി മാത്രം ഉപയോഗിച്ച് സമയസങ്കീർണ്ണതയിൽ വ്യത്യാസമില്ലാതെ മെർജ് സോർട്ടിന്‌ ക്രമീകരണം നടത്താൻ സാധിക്കും. ലിങ്ക്ഡ് ലിസ്റ്റുകളിൽ സോർട്ടിങ്ങ് നടത്താൻ ക്വിക്ക് സോർട്ട് വളരെയധികം സമയമെടുക്കുന്നു. ഹീപ് സോർട്ടിന്‌ ലിങ്ക്ഡ് ലിസ്റ്റുകൾ സോർട്ട് ചെയ്യാനേ കഴിയില്ല.

ഇതും കാണുക[തിരുത്തുക]

"http://ml.wikipedia.org/w/index.php?title=മെർജ്_സോർട്ട്&oldid=1810820" എന്ന താളിൽനിന്നു ശേഖരിച്ചത്