इंसर्शन सॉर्ट

बाईं ओर एक सॉर्टेड हिस्सा बनाता है, एक बार में एक वैल्यू। हर नई वैल्यू बाहर निकालकर तब तक बाईं ओर खिसकाई जाती है जब तक कोई छोटी वैल्यू न मिले।

• सर्वश्रेष्ठ Ω(n)
• औसत Θ(n²)
• सबसे खराब O(n²)
• मेमोरी O(1)
• स्टेबल
• अतिरिक्त मेमोरी नहीं चाहिए

इनका मतलब क्या है?

• सर्वश्रेष्ठ: जब इनपुट इस एल्गोरिदम के लिए सबसे आसान हो, तब लिस्ट के आकार n के साथ समय कैसे बढ़ता है।
• औसत: n के साथ समय की आम बढ़त। n² में वैल्यू की संख्या दोगुनी होने पर लगभग चार गुना समय लगता है; n log n बहुत धीरे बढ़ता है।
• सबसे खराब: सबसे कठिन इनपुट पर बढ़त। तब काम का, जब रफ़्तार कभी नहीं गिरनी चाहिए।
• मेमोरी: लिस्ट के अलावा कितनी अतिरिक्त मेमोरी चाहिए। 1 यानी कुछ वेरिएबल, n यानी लिस्ट की एक कॉपी।
• स्टेबल: दो बराबर वैल्यू अपना मूल क्रम बनाए रखती हैं। रिकॉर्ड के किसी एक फ़ील्ड से सॉर्ट करते समय यह ज़रूरी है।
• अतिरिक्त मेमोरी नहीं चाहिए: लिस्ट के अंदर ही सॉर्ट करता है, दूसरी लिस्ट के बिना।