Sachverhalt:
A.
A.a. Die X._ AG ist eine Aktiengesellschaft mit Sitz in A._. Sie bezweckt insbesondere die Beratung von Personen, Unternehmen und Institutionen des privaten und öffentlichen Rechts in Fragen des Schulden- und Forderungsmanagements, die Entwicklung von Strategien, Methoden und Konzepten für die Bewirtschaftung von Forderungen und Schulden sowie die Erbringung von Beratungsdienstleistungen zur Verbesserung und Erleichterung der Schuldenbewirtschaftung und bei der Erfüllung von internationalen Schulden- und Schuldendienstverpflichtungen.
A.b. Die Tschechische Republik, handelnd durch ihr Finanzministerium, schloss am 22. März 2001 mit der X._ AG ein "Option Agreement" betreffend eine Forderung der Tschechischen Republik gegen die ehemalige Bundesrepublik Jugoslawien. Über einen Teil dieser Forderung hatte die Tschechische Republik bereits verfügt; im " Option Agreement " verpflichtete sie sich für den Fall, dass sie inskünftig die Tilgung der Restforderung in Betracht ziehe, vorab der X._ AG den Kauf der Forderung anzubieten. Diese verpflichtete sich im Gegenzug, gegenüber dem Finanzministerium innerhalb von 60 Kalendertagen nach Eingang des Angebots schriftlich dazu Stellung zu nehmen, widrigenfalls das Finanzministerium berechtigt wäre, über die Forderung anderweitig zu verfügen.
A.c. Mit Schreiben vom 18. Juli 2003 teilte das Finanzministerium der Tschechischen Republik der X._ AG mit, die Tschechische Republik beabsichtige, einen Vertrag mit einem Dritten abzuschliessen, um ihre Staatsforderung gegen die ehemalige Bundesrepublik Jugoslawien (nunmehr gegen die Republik Serbien und Montenegro) zu regulieren. Es sei ein Angebot für eine Regulierung dieser Forderungen in der Höhe von 13 % derselben eingegangen. Das Finanzministerium ersuchte die X._ AG um Mitteilung " mit einem beglaubigten Schreiben ", spätestens bis zum 31. Juli 2003 eintreffend, ob sie den noch verbleibenden Forderungsteil zu vergleichbaren Bedingungen kaufen oder aber das Finanzministerium der Tschechischen Republik von seinen Pflichten aus dem "Option Agreement" ohne Haftung befreien möchte.
Mit Faxschreiben an den Generaldirektor des Tschechischen Finanzministeriums vom 28. Juli 2003 teilte die X._ AG mit, dass sie am Kauf von 75 % der Schuld interessiert sei, und ersuchte um Terminvorschläge für ein Treffen, um das Geschäft abzuwickeln.
A.d. In der Folge stellte sich die X._ AG auf den Standpunkt, es sei gestützt auf diesen Vorgang ein Vertrag zur Abtretung der Forderung zustande gekommen, woraus die Tschechische Republik verpflichtet sei, ihr eine entsprechende Abtretungsurkunde zu übersenden. Die Tschechische Republik bestritt das Zustandekommen eines solchen Vertrags.
B.
B.a. Mit Klage vom 21. Dezember 2007 an das Kantonsgericht von Appenzell Ausserrhoden beantragte die X._ AG (Klägerin) im Hauptbegehren, die Tschechische Republik (Beklagte) sei zu verurteilen, ihr mindestens USD 13'171'649.30 (entsprechend 13'171'649.30 Clearing-Koruna, "XCS") bzw. den entsprechenden Betrag in Landeswährung zu bezahlen, sowie mindestens 45 % von 75 % sämtlicher auf der gesamten Forderung der Beklagten gegen die ehemalige Bundesrepublik Jugoslawien in der Höhe von USD 54'881'926.28 (entsprechend XCS 54'881'926.28) aufgelaufenen und aufgerechneten Zinsen bzw. den entsprechenden Betrag in Landeswährung, abzüglich des durchschnittlichen Anlagebetrages des Betrages von USD 5'351'000.81 (entsprechend XCS 5'351'000.81) seit 28. Juli 2003, zuzüglich Zins zu 5 % seit 31. Mai 2007.
Das Kantonsgericht von Appenzell Ausserrhoden bejahte seine örtliche und sachliche Zuständigkeit und die Anwendbarkeit von tschechischem Recht in der Sache. Es ordnete die Durchführung eines Beweisverfahrens an und holte beim Schweizerischen Institut für Rechtsvergleichung eine Offerte für die Erstellung eines Rechtsgutachtens zur Klärung aller entscheidrelevanten Fragen zum Tschechischen Recht ein. Wegen der voraussichtlich hohen Kosten und langen Dauer der Begutachtung sah die Verfahrensleitung indes davon ab und schlug den Parteien stattdessen die Anwendung schweizerischen Rechts als Ersatzrecht vor. Die Klägerin erklärte sich damit einverstanden, während die Beklagte die Anwendung schweizerischen Rechts als Ersatzrecht ablehnte und den Erlass eines Vorentscheids über die von ihr bestrittene örtliche und sachliche Zuständigkeit des Kantonsgerichts beantragte.
Mit Zwischenentscheid vom 25. Januar 2011 bejahte das Kantonsgericht Appenzell Ausserrhoden seine örtliche und sachliche Zuständigkeit.
B.b. Mit Eingabe vom 11. Februar 2011 focht die Beklagte (Appellantin) den Zwischenentscheid des Kantonsgerichts beim Obergericht von Appenzell Ausserrhoden mit Berufung nach Massgabe der schweizerischen Zivilprozessordnung (ZPO) an. Sie beantragte die Aufhebung des kantonsgerichtlichen Zwischenentscheids sowie Nichteintreten auf die Klage. Die Klägerin (Appellatin) beantragte Abweisung des Rechtsmittels sowie die Feststellung, dass das Kantonsgericht für die Beurteilung der Streitsache zuständig sei. Das Obergericht behandelte das Rechtsmittel als Appellation nach Massgabe der bis 31. Dezember 2011 in Kraft stehenden Zivilprozessordnung des Kantons Appenzell Ausserrhoden vom 27. April 1980 (ZPO/AR).
Mit Urteil vom 21. Mai 2012, versandt am 16. Oktober 2012, hiess das Obergericht die Appellation gut, hob den angefochtenen Entscheid auf und stellte fest, dass die Gerichte des Kantons Appenzell Ausserrhoden zur Beurteilung der Streitsache nicht zuständig seien.
C.
Mit Eingabe vom 16. November 2012 führt die X._ AG (Beschwerdeführerin) gegen das Urteil des Obergerichts von Appenzell Ausserrhoden von 21. Mai 2012 Beschwerde in Zivilsachen an das Bundesgericht mit dem Antrag, den angefochtenen Entscheid aufzuheben, die Unzuständigkeitseinrede abzuweisen und festzustellen, dass die Gerichte des Kantons Appenzell Ausserrhoden zur Beurteilung der Forderung der Beschwerdeführerin zuständig seien; eventualiter sei das Verfahren an die Vorinstanz zur Entscheidung, insbesondere zur Durchführung eines Beweisverfahrens, zurückzuweisen.
Mit Beschwerdeantwort vom 31. Januar 2013 beantragt die Tschechische Republik (Beschwerdegegnerin) Abweisung der Beschwerde, soweit Eintreten.
Die Vorinstanz verzichtete auf Stellungnahme.
Die Parteien reichten Replik und Duplik ein.
D.
Mit Präsidialverfügung vom 17. Dezember 2012 wurde das Gesuch um Erteilung der aufschiebenden Wirkung abgewiesen.

Erwägungen:
1.
Das Bundesgericht prüft von Amtes wegen und mit freier Kognition, ob ein Rechtsmittel zulässig ist (<ref-ruling> E. 1; <ref-ruling> E. 1 S. 103, 470 E. 1 S. 472; <ref-ruling> E. 1 S. 216).
1.1. Die Beschwerde richtet sich gegen einen verfahrensabschliessenden Rechtsmittelentscheid eines oberen kantonalen Gerichts (<ref-law> i.V.m. <ref-law>). Sie ist innert der Beschwerdefrist (<ref-law>) von der mit ihren Rechtsbegehren unterlegenen Partei (<ref-law>) eingereicht worden. Bei der Streitsache handelt es sich um eine Zivilsache (<ref-law>) mit einem Streitwert von weit über Fr. 30'000.-- (<ref-law>). Auf die Beschwerde ist unter Vorbehalt einer rechtsgenügenden Begründung (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG) einzutreten.
1.2. Mit der Beschwerde in Zivilsachen kann u.a. die Verletzung von Bundesrecht einschliesslich Bundesverfassungsrecht gerügt werden (<ref-law>; <ref-ruling> E. 1.2 S. 382 f.). Nicht zu den in <ref-law> vorgesehenen Rügegründen gehört hingegen die Verletzung kantonalen Rechts, dessen Anwendung und Auslegung das Bundesgericht einzig unter dem Blickwinkel eines Verstosses gegen Bundesrecht oder gegen Bundesverfassungsrecht beurteilen kann (<ref-ruling> E. 2.4 S. 249; <ref-ruling> E. 4.3 S. 521 f.; <ref-ruling> E. 1.2 S. 382 f.).
1.3. Das Bundesgericht wendet das Recht zwar von Amtes wegen an (<ref-law>; vgl. dazu <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Es prüft dabei aber nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 1.4.1 S. 400; <ref-ruling> E. 1.1 S. 104 f.). In der Beschwerdeschrift ist in gedrängter Form darzulegen, inwiefern der angefochtene Entscheid Recht verletzt (<ref-law>). Aus den materiellrechtlichen Rügen muss zumindest sinngemäss ersichtlich sein, inwieweit der angefochtene Entscheid nach Ansicht der Beschwerdeführerin bundesrechtliche Normen verletzen soll, wenn der von der Vorinstanz verbindlich festgestellte - und nicht lediglich ein von der Beschwerdeführerin behaupteter abweichender - Sachverhalt zugrunde gelegt wird (<ref-law>).
1.4. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Dazu gehören sowohl die Feststellungen über den Lebenssachverhalt, der dem Streitgegenstand zugrunde liegt, als auch jene über den Ablauf des vor- und erstinstanzlichen Verfahrens, namentlich die Parteivorbringen in denselben (Urteile 4A_210/2009 vom 7. April 2010 E. 2; 4A_439/2010 vom 20. Oktober 2011 E. 2.1). Das Bundesgericht kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.5 S. 401); macht der Beschwerdeführer eine Verletzung des Willkürverbots (<ref-law>) geltend, genügt es nicht, wenn er einfach behauptet, der angefochtene Entscheid sei willkürlich. Er hat vielmehr im Einzelnen zu zeigen, inwiefern der angefochtene Entscheid offensichtlich unhaltbar ist (<ref-ruling> E. 3 S. 352; <ref-ruling> E. 5.5 S. 5). Überdies hat er darzutun, inwiefern die Behebung des gerügten Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 2.2.2 S. 22). Dies gilt auch, wenn im Zusammenhang mit einer Sachverhaltsrüge eine Verletzung des rechtlichen Gehörs geltend gemacht wird, wobei glaubhaft zu machen ist, dass bei korrekter Vorgehensweise der Entscheid anders hätte ausfallen müssen (<ref-ruling> E. 3.4 S. 125; anders noch: Urteil 1C_397/2008 vom 12. Januar 2009 E. 2.1 unter Zugrundelegung der formellen Natur des Gehörsanspruchs). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>), was in der Beschwerde näher darzulegen ist (<ref-ruling> E. 3 S. 395).
2.
Die Beschwerdeführerin rügt Verletzungen des kantonalen Prozessrechts im obergerichtlichen Verfahren in dreifacher Hinsicht: eine willkürliche Ausdehnung der Appellationsfrist, eine willkürliche Änderung der Entscheidungsgrundlage sowie eine willkürliche Verletzung der Dispositionsmaxime. Die Beschwerdeschrift erfüllt indes weder die an eine Willkürrüge gestellten Anforderungen, noch wird in ihr dargelegt, inwiefern die Behebung der gerügten Mängel für den Ausgang des Verfahrens entscheidend sein könnte. Auf die behaupteten Verletzungen von kantonalem Prozessrecht im obergerichtlichen Verfahren kann mithin nicht eingetreten werden.
3.
3.1. Der bestrittene Gegenstand des angefochtenen Entscheids ist die internationale und örtliche Zuständigkeit des Kantonsgerichts von Appenzell Ausserrhoden. Die Beschwerdeführerin will eine solche aus <ref-law> ableiten. Diese Norm lautete in der zum Zeitpunkt der Einleitung der Klage am 21. Dezember 2007 geltenden Fassung wie folgt:
"Hat der Beklagte weder Wohnsitz oder gewöhnlichen Aufenthalt, noch eine Niederlassung in der Schweiz, ist aber die Leistung in der Schweiz zu erbringen, so kann beim schweizerischen Gericht am Erfüllungsort geklagt werden."
In ihrer auf den 1. Januar 2011 in Kraft gesetzten Fassung lautet die Bestimmung:
"Ist die für den Vertrag charakteristische Leistung in der Schweiz zu erbringen, so kann auch beim schweizerischen Gericht am Erfüllungsort dieser Leistung geklagt werden."
Die Vorinstanz hat zutreffend erwogen, dass die sich hier stellende Zuständigkeitsfrage in Anwendung von <ref-law> nach Massgabe beider Gesetzesfassungen zu prüfen ist; in Bezug auf den hier einzig strittigen Begriff des Erfüllungsortes hat sie keinen Unterschied der beiden Gesetzesfassungen ausgemacht.
3.2. In einem ersten Schritt prüfte die Vorinstanz, ob ein Vertragsverhältnis bestehe, welches die Parteien zu entsprechenden Erfüllungshandlungen verpflichten würde. Ungeachtet dieses Befundes unterstellte die Vorinstanz in einem zweiten Schritt die von der Beschwerdeführerin behauptete vertragliche Verpflichtung der Beschwerdegegnerin zur Abtretung ihrer Staatsforderung gegen die ehemalige Bundesrepublik Jugoslawien und verneinte auch bei dieser für die Beschwerdeführerin günstigsten Ausgangslage eine Zuständigkeit der Gerichte des Kantons Appenzell Ausserrhoden.
3.3. Die Beschwerdeführerin wendet sich gegen die vorinstanzliche Verneinung eines gültigen Forderungskaufvertrages und behauptet namentlich eine willkürliche Feststellung des Sachverhalts sowie eine ungenügende Berücksichtigung des Tschechischen Rechts. Wie es sich damit verhält, kann indes offen bleiben, weil sich aus den folgenden Erwägungen ergibt, dass die Vorinstanz auch bei Unterstellung des von ihr verneinten Anspruchs der Beschwerdeführerin auf Abtretung der Staatsforderung eine Zuständigkeit der Gerichte des Kantons Appenzell Ausserrhoden zutreffend verneint hat.
4.
Das Bundesgericht hat bislang die Frage offen gelassen, ob der in <ref-law> verwendete Anknüpfungsbegriff des Erfüllungsortes lege fori oder lege causae zu bestimmen sei (<ref-ruling> E. 3.4 S. 745 ff. m.w.H.; in <ref-ruling> E. 4.1 S. 467 wurde ohne weitere Begründung auf die lex fori abgestellt; vgl. zum Meinungsstand in der Lehre AMSTUTZ/WANG/GOHARI, in: Basler Kommentar, 3. Aufl. 2013, N. 13-13c zu <ref-law>). Die Vorinstanz kam unter Hinweis auf § 567 Abs. 1 des Tschechischen Bürgerlichen Gesetzbuches und § 336 Satz 1 des Tschechischen Handelsgesetzbuches zum Schluss, dass bezüglich der sachrechtlichen Bestimmung des Erfüllungsortes das Tschechische Recht dem schweizerischen entspreche, was vor Bundesgericht von keiner Partei in Zweifel gezogen wird. Die Frage, ob der Anknüpfungsbegriff nach der lex fori oder der lex causae auszulegen ist, kann deshalb weiterhin offen bleiben, denn es wird sich im Folgenden erweisen, dass die Vorinstanz das schweizerische Recht korrekt angewendet hat.
4.1. In Frage steht der Erfüllungsort einer Verpflichtung zur Abtretung einer Forderung. Die Vorinstanz ist von der Massgeblichkeit von <ref-law> ausgegangen. Diese Bestimmung sieht vor, dass alle Verbindlichkeiten mit Ausnahmen von Geldschulden (für diese gilt <ref-law>) und Speziesschulden (für diese gilt <ref-law>) an dem Orte zu erfüllen sind, wo der Schuldner zur Zeit ihrer Entstehung seinen Wohnsitz oder Sitz hatte.
Die Beschwerdeführerin wirft der Vorinstanz eine fehlerhafte Anwendung von <ref-law> vor. Sie macht namentlich geltend, bei der vorliegend geschuldeten Abgabe einer empfangsbedürftigen Willenserklärung befinde sich der Erfüllungsort am Wohnsitz oder Sitz des Empfängers.
4.2. Der von der Beschwerdeführerin behauptete - und von der Vorinstanz zum Zwecke der Prüfung der Zuständigkeitsfrage als bestehend unterstellte - Anspruch geht auf Leistung einer Abtretungserklärung. Diese bedarf zu ihrer Gültigkeit der schriftlichen Form (<ref-law>), während die Verpflichtung zum Abschluss eines Abtretungsvertrages ( pactum de cedendo ) formlos begründet werden kann (<ref-law>). Die sich aus dem pactum de cedendoergebende Leistungspflicht des Zedenten besteht in der Ausstellung einer Zessionsurkunde, welche die Abtretungserklärung beurkundet, und in der Begebung der Urkunde an den Zessionar ( HERMANN BECKER, in: Berner Kommentar, 2. Aufl. 1941, N. 3 zu <ref-law>).
4.3. Die Beschwerdeführerin macht geltend, wegen der Empfangsbedürftigkeit der mit der Zessionsurkunde verbrieften Willenserklärung verschiebe sich der Erfüllungsort für den Abtretungsakt auf den Sitz des Zessionars.
Dem kann nicht gefolgt werden: Nach Massgabe von <ref-law> wäre die im vorliegenden Fall unterstellte Verpflichtung zum Abschluss eines Abtretungsvertrages durch die Ausstellung und Begebung einer Zessionsurkunde am Sitz der Beschwerdegegnerin als Schuldnerin zu erfüllen. Dort hätte die Beschwerdegegnerin die Urkunde zu errichten und der Beschwerdeführerin zur Verfügung zu halten bzw. von dort aus zu versenden. Daran ändert - entgegen der Auffassung der Beschwerdeführerin - hinsichtlich des Erfüllungsortes nichts, dass die in der Zessionsurkunde verkörperte Willenserklärung empfangsbedürftig ist, und dass der Zessionar auf den erst durch Erhalt der Zessionsurkunde geschaffenen Besitz derselben angewiesen ist, damit er die ihm abgetretene Forderung gegenüber dem debitor cessus geltend machen kann. Zudem darf nach Treu und Glauben Wirksamkeit der Abtretung im Zeitpunkt der Versendung der Zessionsurkunde angenommen werden, wenn der Zessionar aufgrund des pactum de cedendo mit der Abtretung rechnet oder gar darauf drängt, und seine Zustimmung deshalb als antizipiert erteilt gelten kann ( EUGEN BUCHER, Schweizerisches Obligationenrecht Allgemeiner Teil, 2. Aufl. 1988, S. 547 f. und 550 f.).
4.4. Die Beschwerdeführerin bringt weiter vor, die Vorinstanz habe sich in unzulässiger antizipierter Beweiswürdigung dem angebotenen Beweismittel einer Zeugenaussage ihrer Tschechischen Rechtsvertreterin verschlossen. Dadurch hätte der Beweis erbracht werden können, dass die Beschwerdegegnerin sich verpflichtet habe, die Zessionsurkunde nach A._ zu senden.
In formeller Hinsicht genügt die Rüge den Anforderungen an eine Willkürrüge nicht. In der Sache verkennt sie, dass bei Annahme einer Versendungsschuld der Erfüllungsort sich am Sitz der Beschwerdegegnerin als Versendungsort und nicht in A._ als Bestimmungsort befände.
4.5. Damit hat die Vorinstanz Bundesrecht zutreffend angewandt, indem sie einen Zuständigkeit begründenden Erfüllungsort in A._ verneinte.
5.
Erstmals in ihrer Beschwerdeentwickelt die Beschwerdeführerin sodann ansatzweise das Argument, dass ein Gerichtsstand in A._ möglicherweise gestützt auf Ansprüche aus culpa in contrahendo gegeben sei, und wirft der Vorinstanz vor, diesbezüglich keine tatsächlichen Feststellungen getroffen zu haben. Sie unterlässt es dabei freilich darzulegen, gestützt auf welche ihrer Vorbringen sich auf einen solchen Gerichtsstand schliessen liesse, und behauptet selber nicht, einen Anspruch aus culpa in contrahendo im kantonalen Verfahren schlüssig vorgetragen zu haben. Auf die Rüge kann nicht eingetreten werden.
6.
Die Beschwerde erweist sich damit insgesamt als unbegründet und ist abzuweisen.
Diesem Ausgang des Verfahrens entsprechend wird die Beschwerdeführerin kosten- und entschädigungspflichtig (Art. 66 Abs. 1 und Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 40'000.-- werden der Beschwerdeführerin auferlegt.
3.
Die Beschwerdeführerin hat die Beschwerdegegnerin für das bundesgerichtliche Verfahren mit Fr. 50'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Obergericht von Appenzell Ausserrhoden, 1. Abteilung, schriftlich mitgeteilt.
Lausanne, 21. Oktober 2013
Im Namen der I. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Präsidentin: Klett
Der Gerichtsschreiber: Hurni