[సంగీతాన్ని] డౌ LLOYD: OK, కాబట్టి కలిసిపోయినా విధమైన మరో అల్గోరిథం మేము బయటికి ఉపయోగించే వ్యూహం యొక్క అంశాలు. మేము చూస్తారు కానీ, అది సంపాదించి ఒక చాలా ప్రాథమిక వ్యత్యాసం ఎంపిక విధమైన, బబుల్ నుండి విధమైన, మరియు చొప్పించడం విధమైన అది నిజంగా అందంగా తెలివైన తయారు. విలీనం వెనుక ప్రధాన ఆలోచన విధమైన చిన్న శ్రేణుల క్రమం ఉంది ఆపై ఆ శ్రేణుల మిళితం కలిసి, లేదా them-- విలీనం అందుకే క్రమబద్ధీకరించబడతాయి క్రమంలో పేరు అనుకుందాం. విధమైన చేస్తుంది విలీనం ఆ విధంగా ఈ సాధనం పరపతి ద్వారా ఉంది ఏమిటి ఇది సూత్రం అని మేము వెంటనే గురించి మాట్లాడటం కావడం చేస్తున్నారు కానీ మేము నిజంగా ఇంకా గురించి మాట్లాడారు లేదు. ఇక్కడ విలీనంతో విధమైన వెనుక ప్రధాన ఆలోచన. , శ్రేణి యొక్క ఎడమ అర్ధ క్రమీకరించు n ఊహిస్తూ 1 కంటే ఎక్కువ. నేను చెప్పినప్పుడు ఏమి అర్థం n ఊహిస్తూ, 1 కంటే ఎక్కువ మనం అంగీకరిస్తున్నారు భావిస్తున్నాను ఆ వ్యూహంలో ఉంటే కేవలం ఒకే అంశం ఉన్నాయి, అది క్రమబద్ధీకరించబడతాయి. మేము నిజానికి అవసరం లేదు దానికి ఏదైనా చేయాలని. మేము దానిని వేరు చేయడానికి ప్రకటించవచ్చు. ఇది కేవలం ఒకే మూలకం. సో pseudocode, మళ్ళీ, , శ్రేణి యొక్క ఎడమ అర్ధ క్రమం అప్పుడు కుడి సగం అర్రే క్రమం, అప్పుడు కలిసి రెండు విభజించటం విలీనం. ఇప్పుడు, ఇప్పటికే మీరు కావచ్చు ఆలోచిస్తూ, అది రకమైన కేవలం ఉన్నారు మీరు ఆఫ్ పెట్టటం చేస్తున్నారు లాగా మీరు నిజంగా ఏదైనా చేయడం లేదు. మీరు ఎడమ క్రమం చెబుతున్న సగం కుడి సగం క్రమం, కానీ మీరు చెప్పడం లేదు నాకు ఎలా మీరు చేయుచున్నారు. కానీ కాలం గుర్తుంచుకోవాలి వ్యూహం ఒకే మూలకం, మేము క్రమబద్ధీకరించబడతాయి ప్రకటించవచ్చు. అప్పుడు మేము వాటిని కలిసి మిళితం చేయవచ్చు. మరియు ఆ నిజానికి విలీనంతో విధమైన వెనుక ప్రాథమిక ఆలోచన, కాబట్టి అది విచ్ఛిన్నం ఉంది మీ శ్రేణుల పరిమాణం ఒకటి ఉన్నాయి. ఆపై మీరు అక్కడ నుండి పునర్నిర్మాణం. విధమైన ఖచ్చితంగా విలీనం ఒక క్లిష్టమైన అల్గోరిథం. మరియు అది కూడా కొద్దిగా వార్తలు చూసేందుకు క్లిష్టమైన. సో ఆశాజనక, విజువలైజేషన్ నేను మీరు వెంట అనుసరించండి సహాయం చేస్తుంది ఇక్కడ ఉన్నాయి. మరియు నేను విషయాలు వ్యాఖ్యానం నా ఉత్తమ ప్రయత్నిస్తాము మరియు ఈ ఒక కొంచెం ద్వారా ముందుకు నెమ్మదిగా ఇతర వాటి కంటే కేవలం ఆశాజనక మీ తల పొందడానికి విలీనంతో విధమైన వెనుక ఆలోచనలు చుట్టూ. కాబట్టి మేము అదే వ్యూహం కలిగి ఇతర సార్టింగ్ అల్గోరిథం వీడియోలను మీరు చూసిన ఉంటే them-- ఆరు మూలకం శ్రేణి. మరియు ఇక్కడ మా pseudocode కోడ్ విధమైన ఉంది ఎడమ సగం, కుడి సగం క్రమం, కలిసి రెండు విభజించటం విలీనం. కాబట్టి యొక్క ఈ చాలా చీకటి ఇటుక ఎరుపు తీసుకుందాం శ్రేణి మరియు అది వదిలి సగం క్రమం. ప్రస్తుతానికి కాబట్టి, మేము వెళుతున్న కుడివైపున అంశాలు విస్మరించడానికి. ఇది ఉంది, కానీ మేము ఉన్నాము ఇంకా ఆ అడుగు వద్ద. మేము ఉన్నాము వద్ద విధమైన యెరే యొక్క కుడి సగం. మేము విధమైన ఎడమ వద్ద ఉన్నాము అర్రే సగం. మరియు కేవలం కొరకు ఒక కొంచెం ఎక్కువ ఉండటం స్పష్టమైన, నేను సూచించవచ్చు ఏమి దశకు మేము ఉన్నాము, నేను మారడానికి వెళుతున్న నారింజ ఈ సెట్ రంగు. ఇప్పుడు, మేము ఇప్పటికీ గురించి మాట్లాడటం చేస్తున్నాం అసలు శ్రేణి అదే లెఫ్ట్ హాఫ్. కానీ నేను సామర్థ్యం ద్వారా ఆ ఆశతో వెబ్ వివిధ అంశాల రంగులు చూడండి అది కొంచెం చేస్తాము ఇక్కడ జరగబోతోంది ఏమి క్లియర్. OK, కాబట్టి ఇప్పుడు మేము ఒక మూడు మూలకం శ్రేణి. మేము ఈ ఎడమ సగం క్రమం ఎలా ఇప్పటికీ ఈ దశను శ్రేణిలో, ఇది? మేము ఎడమ క్రమం ప్రయత్నిస్తున్న ఇటుక ఎరుపు శ్రేణి సగం ఎడమ వీటిలో సగం నేను ఇప్పుడు నారింజ రంగు చేసిన. Well, మేము ప్రయత్నించండి మరియు కాలేదు మళ్ళీ ఈ విధానాన్ని పునరుక్తి. కాబట్టి మేము ఇంకా ఉన్నాము క్రమం ప్రయత్నిస్తున్న మధ్యలో పూర్తి శ్రేణి యొక్క ఎడమ సగం. యొక్క ఎడమ అర్ధ అర్రే, నేను వెళుతున్నాను ఏకపక్ష నిర్ణయానికి ఎడమ భాగంలో కుడి సగం కంటే తక్కువగా ఉంటుంది, ఈ ఏమవుతుంది ఎందుకంటే మూడు అంశాలు ఉంటాయి. కాబట్టి నేను ఆ చెప్పటానికి వెళుతున్న ఎడమ సగం శ్రేణి యొక్క ఎడమ అర్ధ కేవలం మూలకం ఐదు ఉంది. ఐదు, ఒకే మూలకం అర్రే, మేము అది క్రమం ఎలా. కాబట్టి అయిదు క్రమబద్ధీకరించబడింది. మేము కేవలం ప్రకటిస్తుంది చూడాలని. ఇది ఒక మూలకం శ్రేణి. కాబట్టి మేము ఇప్పుడు క్రమబద్ధీకరించబడతాయి చేసిన ఎడమ half-- యొక్క ఎడమ అర్ధ లేదా, మేము క్రమబద్ధీకరించబడతాయి చేసిన నారింజ లెఫ్ట్ హాఫ్. కాబట్టి ఇప్పుడు, క్రమంలో ఇప్పటికీ పూర్తి మొత్తం శ్రేణి యొక్క ఎడమ అర్ధ మేము సగం క్రమం అవసరం నారింజ లేదా ఈ విషయాన్ని. మేము ఎలా చెయ్యాలి? Well, మేము ఒక రెండు మూలకం శ్రేణి కలిగి. కాబట్టి మేము ఎడమ సగం క్రమం చేయవచ్చు రెండు యెరే యొక్క. రెండు ఒకే అంశం. కనుక ఇది అప్రమేయంగా క్రమబద్ధీకరించబడతాయి. అప్పుడు మేము కుడి సగం క్రమం చేయవచ్చు శ్రేణి, ఒక యొక్క ఆ భాగంను. ఆ అప్రమేయంగా విధమైన వార్తలు. ఈ ఇప్పుడు మొదటి సారి మేము కలిసిపోయినా అడుగు చేరుకున్నారు. మేము అయితే, పూర్తి చేసిన మేము ఇప్పుడు రకమైన down-- యున్న చేస్తున్న మరియు ఆ గమ్మత్తైన విధమైన వార్తలు సూత్రం తో విషయం, మీరు మీ ఉంచాలని అవసరం మేము ఎక్కడ గురించి అధిపతి. కాబట్టి మేము ఎడమ విధమైన చేసిన నారింజ భాగం సగం. మరియు ఇప్పుడు, మేము క్రమబద్ధీకరించేందుకు మధ్యలో ఉన్నాము నారింజ భాగం కుడి సగం. మరియు ఆ ప్రక్రియలో, మనం అడుగు ఉండాలి ఇప్పుడు గురించి, కలిసి రెండు విభజించటం విలీనం. మేము రెండు విభజించటం చూస్తున్నప్పుడు యెరే యొక్క, మేము రెండు మరియు ఒక చూడండి. ఏ మూలకం తక్కువగా ఉంది? వన్. అప్పుడు మూలకం తక్కువగా ఉంది? సరే, రెండు లేదా ఏమీ వార్తలు. కనుక ఇది రెండు వార్తలు. కాబట్టి ఇప్పుడు, కేవలం మళ్ళీ ఫ్రేమ్ మేము సందర్భం లో ఉన్న, మేము క్రమబద్ధీకరించబడతాయి చేశారు నారింజ యొక్క ఎడమ అర్ధ మరియు మూలం కుడి సగం. నేను రంగులు మార్చారు తెలుసు మేము ఉన్న మళ్ళీ, కానీ ఆ. మరియు కారణం నేను చేసింది ఈ ప్రక్రియ ఎందుకంటే డౌన్ iterating, కొనసాగించడాన్ని వెళుతున్న. మేము ఎడమ క్రమబద్ధీకరించబడతాయి చేసిన మాజీ నారింజ సగం మాజీ నారింజ కుడి సగం. ఇప్పుడు, మేము ఆ విలీనం అవసరం కలిసి చాలా రెండు విభజించటం. ఆ మేము ఉన్నాము అడుగు ఉంది. కాబట్టి మేము అన్ని పరిగణలోకి ఇప్పుడు ఆకుపచ్చ ఉండే మూలకాలను అసలు శ్రేణి యొక్క ఎడమ అర్ధ. మరియు మేము ఆ విలీనం అదే విధానాన్ని ఉపయోగించి మేము రెండు విలీనం చేసినట్టే మరియు ఒక కేవలం ఒక క్షణం క్రితం. ఎడమ భాగంలో చిన్న ఎడమ అర్ధభాగంలో మూలకం ఐదు ఉంది. చిన్న అంశం మీద కుడి సగం ఒకటి. ఆ చిన్న ఉంది? వన్. చిన్న అంశం మీద ఎడమ సగం ఐదు ఉంది. చిన్న అంశం మీద కుడి సగం రెండు ఉంది. చిన్న ఏమిటి? రెండు. మరియు తర్వాత చివరగా ఐదు మరియు ఏమీ మేము ఐదు చెప్పగలను. OK, కాబట్టి పెద్ద చిత్రాన్ని, లెట్స్ రెండవ కోసం ఒక విరామం తీసుకుందామని మేము ఎక్కడ గుర్తించడానికి. మేము నుండి ప్రారంభించారు ఉంటే చాలా ప్రారంభంలో, మేము ఇప్పుడు కోసం పూర్తిచేసుకున్న మొత్తం శ్రేణి కేవలం ఇక్కడ pseudocode కోడ్ ఒకటి అడుగు. మేము పరిష్కరించబడి యెరే యొక్క ఎడమ సగం. అసలు గుర్తుచేసుకున్నారు ఆర్డర్ ఐదు, రెండు, ఒకటి. ఈ ప్రక్రియ ద్వారా వెళ్ళడం ద్వారా మరియు డౌన్ గూడు మరియు పునరావృత, సమస్య తొలగించేందుకు నిరంతర డౌన్ చిన్న మరియు చిన్న భాగాలుగా, మేము ఇప్పుడు పూర్తి చేసిన pseudocode ఒకటి దశను మొత్తం ప్రారంభ శ్రేణి కోసం. మేము దాని ఎడమ భాగంలో పరిష్కరించబడి. కాబట్టి ఇప్పుడు యొక్క అక్కడ స్తంభింప తెలియజేయండి. ఇప్పుడు యొక్క కుడి విధమైన వీలు అసలు శ్రేణి సగం. మరియు మేము ఆ చేయబోతున్నామని అదే పునరుత్థాన ద్వారా వెళుతున్న విషయాలు విడగొట్టి ప్రక్రియ ఆపై వారిద్దరూ కలిసి విలీనం. కాబట్టి యొక్క ఎడమ అర్ధ ఎరుపు, లేదా ఎడమ భాగంలో అసలు కుడి సగం అర్రే, నేను చెప్పడానికి వెళుతున్నాను మూడు ఉంది. మళ్ళీ, నేను ఇక్కడ స్థిరమైన ఉండటం నేను. మీరు ఒక బేసి ఉంటే మూలకాల సంఖ్య, అది నిజంగా లేదో పట్టింపు లేదు మీరు ఎడమ ఒకటి చిన్న చేయడానికి లేదా కుడి ఒక చిన్న. ఏ మంచిని ఉంది చేసినప్పుడు మీరు ఆ జరిపి ఈ సమస్య ఎదుర్కునే కలిసిపోయినా, మీరు స్థిరమైన ఉండాలి. మీరు గాని ఎల్లప్పుడూ అవసరం ఒక ఎడమవైపు చిన్న చేయడానికి లేదా ఎల్లప్పుడూ చేయవలసి కుడివైపు చిన్న. ఇక్కడ, నేను ఎల్లప్పుడూ ఎంచుకున్నారు ఎడమవైపు చిన్న చేయడానికి నా శ్రేణి, లేదా నా ఉప-శ్రేణి, బేసి పరిమాణంలో ఉంటుంది. మూడు ఒకే మూలకం, అందువలన అది క్రమబద్ధీకరించబడింది. మేము ఆ భావన జమచేసి చేసిన మా మొత్తం ప్రక్రియ అంతా ఇప్పటివరకు. కాబట్టి ఇప్పుడు యొక్క కుడి విధమైన వీలు కుడి సగం సగం, లేదా ఎరుపు కుడి సగం. మళ్లీ, మేము ఈ డౌన్ విభజించాల్సి ఉంటుంది. ఈ ఒక మూలకం శ్రేణి కాదు. మేము క్రమబద్ధీకరించబడతాయి డిక్లేర్ కాదు. కాబట్టి మొదటి, మేము వెళుతున్న ఎడమ అర్ధ క్రమం. ఎడమ భాగంలో ఒక మూలకం ఉంది, కాబట్టి అది అప్రమేయంగా విధమైన వార్తలు. అప్పుడు మేము కుడి క్రమం చూడాలని ఒకే మూలకం ఇది సగభాగం ఉంది. ఇది అప్రమేయంగా క్రమబద్ధీకరించబడతాయి. ఇంక ఇప్పుడు, మేము కలిసి ఆ రెండు విలీనం చేయవచ్చు. నాలుగు చిన్న, మరియు అప్పుడు ఆరు తక్కువగా ఉంది. మళ్ళీ, ఏమి మేము ఈ సమయంలో చేసారు? మేము ఎడమ క్రమబద్ధీకరించబడతాయి చేసిన కుడి సగం సగం. లేదా అసలు తిరిగి వెళ్ళడం ఉన్నాయి ఆ రంగులు, మేము ఎడమ క్రమబద్ధీకరించబడతాయి చేసిన మృదువైన ఎరుపు సగం. ఇది నిజానికి ఒక చీకటి ఇటుక ఉంది ఎరుపు మరియు ఇప్పుడు అది ఒక మృదువైన ఎరుపు, లేదా అది ఒక మృదువైన ఎరుపు ఉంది. మరియు తర్వాత మేము క్రమబద్ధీకరించబడతాయి చేసిన మృదువైన ఎరుపు కుడి సగం. ఇప్పుడు బాగా, వారు కేవలం మళ్ళీ ఆకుపచ్చ ఉన్నాము మేము ఒక ప్రక్రియ ద్వారా వెళుతున్న ఎందుకంటే. మరియు మేము మళ్లీ చేయాల్సిన ఈ పైగా మరియు పైగా. కాబట్టి ఇప్పుడు మేము ఆ విలీనం చేయవచ్చు కలిసి రెండు విభజించటం. మరియు మేము ఇక్కడ ఏమి ఉంది. నల్ల లైన్ కాబట్టి కేవలం ఎడమ భాగంలో విభజించబడింది మరియు ఈ విధమైన భాగం కుడి సగం. మేము చిన్న విలువ పోల్చి శ్రేణి యొక్క ఎడమ వైపు లేదా నాకు మన్నించు, చిన్న ఎడమ భాగంలో విలువ కుడి చిన్న విలువ సగం మరియు మూడు ఇతర చిన్న అని కనుగొనడానికి. ఇప్పుడు ఒక ఆప్టిమైజేషన్ యొక్క ఒక బిట్, కుడి? ఏమీ నిజానికి ఉంది ఎడమవైపు వదిలి. మిగిలిన ఏమీ లేదు ఎడమ వైపు, కాబట్టి మేము సమర్ధవంతంగా చెయ్యవచ్చు కేవలం మేము ప్రకటించవచ్చు move-- అది మిగిలిన నిజానికి క్రమబద్ధీకరించబడతాయి మరియు కేవలం అది టాక్ ఏదీ లేదు ఎందుకంటే, న వ్యతిరేకంగా సరిపోల్చండి వేరే. మరియు మేము తెలుసు కుడి వైపు కుడి వైపు క్రమబద్ధీకరించబడింది. OK, కాబట్టి ఇప్పుడు యొక్క మళ్లీ స్తంభింప వీలు మరియు మేము కథలో ఎక్కడ గుర్తించడానికి. మొత్తం శ్రేణిలో, మేము ఏమి సాధించవచ్చు? మేము నిజానికి సాధనకు చేసిన ఇప్పుడు ఒక మరియు అడుగు రెండు వేసింది. మేము ఎడమ సగం క్రమబద్ధీకరించబడతాయి, మేము సగం క్రమబద్ధీకరించబడింది. కాబట్టి ఇప్పుడు, అవశేషాలు మాకు ఉంది కలిసి ఆ రెండు విభజించటం విలీనం చేయడం. కాబట్టి మేము తక్కువ విలువైన సరిపోల్చండి యెరే యొక్క ప్రతి అర్ధ మూలకం మరియు టర్న్ లో వెళ్లండి. వన్ మూడు కంటే తక్కువ, కాబట్టి ఒక వెళ్తాడు. రెండు మూడు కంటే తక్కువ, అందువలన రెండు వెళ్తాడు. మూడు 5 కంటే తక్కువ, కనుక మూడు వెళ్తాడు. నాలుగు 5 కంటే తక్కువ, అందువలన నాలుగు వెళుతుంది. అప్పుడు ఐదు, ఆరు కంటే తక్కువ మరియు ఆరు అన్ని మిగిలిపోయింది. ఇప్పుడు, నాకు తెలుసు, ఆ దశలు చాలా ఉంది. మరియు మేము చాలా నిష్క్రమించారు మా నేపథ్యంలో మెమరీ. మరియు ఆ గ్రే చతురస్రాలు ఉన్నాయి ఏమిటి. ఒక పట్టింది వంటి ఇది బహుశా భావించాడు చొప్పించడం విధమైన కంటే ఎక్కువ చాలా, బబుల్ విధమైన, లేదా ఎంపిక విధమైన. కానీ నిజానికి, ఎందుకంటే ఒక ఈ ప్రక్రియలు చాలా అదే time-- సంభవించే ఇది మళ్ళీ, మేము చేస్తాము ఏదో ఉంది మేము గురించి మాట్లాడినప్పుడు గురించి మాట్లాడటానికి ఒక భవిష్యత్తులో సూత్రం ఆర్జించింది వీడియో నిజానికి ఈ అల్గోరిథం స్పష్టంగా మౌలికంగా ఉంది ఏదైనా కన్నా వేరే మేము ముందు చూసిన కానీ గణనీయంగా కూడా ఉంది మరింత సమర్థవంతంగా. ఎందుకు అని? సరే, చెత్త లో దృష్టాంతంలో, మేము కలిగి n మూలకాలు విడిపోయినట్లు ఆపై వాటిని మళ్లీ చేరుతాయి. కానీ మేము పునఃసంయోగం ఉన్నప్పుడు వాటిని మనం చేస్తున్నా ప్రధానంగా రెట్టింపు ఉంటుంది చిన్న శ్రేణుల యొక్క పరిమాణం. మేము ఒక మూలకం యొక్క ఒక సమూహం కలిగి శ్రేణుల మేము సమర్థవంతంగా రెండు మూలకం శ్రేణుల లోకి మిళితం. మరియు తర్వాత మేము ఆ పడుతుంది రెండు మూలకం శ్రేణుల మరియు వాటిని కలిసి మిళితం అందువలన న నాలుగు మూలకం శ్రేణులను మరియు మరియు అందువలన న, మరియు అందువలన న, మేము వరకు ఒకే n మూలకం శ్రేణి కలిగి. కానీ ఎన్ని doublings అది n ను పడుతుంది? తిరిగి ఫోన్ బుక్ ఉదాహరణ అనుకుంటున్నాను. ఎన్ని సార్లు మేము కూల్చివేసి చేయాలని సగం లో ఫోన్ బుక్, ఎన్ని ఎక్కువ సార్లు మేము ఫోన్ బుక్ కూల్చివేసి ఉన్నాయి సగం లో, ఉంటే ఫోన్ బుక్ యొక్క పరిమాణం రెట్టింపు? కేవలం ఒక కుడి ఉంది? కాబట్టి విధమైన ఉంది ఇక్కడ సంవర్గమాన మూలకం. కానీ మేము కూడా ఇప్పటికీ కలిగి కనీసం n మూలకాలు అన్ని చూడండి. చెత్త దృష్టాంత కాబట్టి విధమైన n లాగ్ n నడుస్తుంది విలీనం. మేము వద్ద చూడండి కలిగి n మూలకాల అన్ని మరియు మేము వాటిని మిళితం కలిగి కలిసి లాగ్ n దశలను సెట్లలో. ఉత్తమ దృష్టాంతంలో, అర్రే సంపూర్ణ క్రమబద్ధీకరించబడింది. ఆ గొప్ప పని. కానీ అల్గోరిథం ఆధారంగా మేము ఇక్కడ కలిగి మేము ఇంకా విడిపోయి పునఃసంయోగం ఉంటుంది. ఈ సందర్భంలో అయితే, తిరిగి కలపటం అసమర్థ యొక్క రకం. ఇది అవసరంలేదు. కానీ మేము ఇంకా ద్వారా వెళ్ళి ఏమైనప్పటికీ మొత్తం ప్రక్రియ. ఉత్తమ సందర్భంలో కాబట్టి మరియు చెత్త సందర్భంలో, ఈ అల్గోరిథం n లాగ్ n సమయం నడుస్తుంది. విలీనం విధమైన ఖచ్చితంగా ఒక బిట్ trickier ఉంది ఇతర ప్రధాన సార్టింగ్ అల్గోరిథంలు కంటే మేము CS50 గురించి మాట్లాడారు కానీ చేసిన చాల ఎక్కువ శక్తివంతమైన. మరియు అలా అయితే మీరు ఎప్పుడైనా కనుగొనేందుకు సందర్భంగా అది అవసరం లేదా ఒక క్రమం దాన్ని ఉపయోగించండి పెద్ద డేటా సెట్ పొందడానికి సూత్రం యొక్క భావన చుట్టూ మీ తల నిజంగా శక్తివంతమైన అవతరిస్తుంది. మరియు అది చేయడానికి జరగబోతోంది మీ కార్యక్రమాలు నిజంగా చాలా సమర్థవంతంగా ఏదైనా వర్సెస్ విధమైన విలీనం ఉపయోగించి. నేను డౌ లాయిడ్ ఉన్నాను. ఈ CS50 ఉంది.