Sachverhalt:
A.
Am 22. Dezember 2016 fuhr A._ mit seinem Personenwagen auf der Autobahn A18 in Fahrtrichtung Basel auf dem Überholstreifen. Kurz vor der Signalisation "Muttenz-Süd 1200m" wechselte er - ohne die Richtungsanzeige zu betätigen - hinter einem roten Personenwagen nach rechts auf die Normalspur und passierte den auf der Überholspur fahrenden roten Personenwagen. A._ näherte sich sodann auf der Normalspur einem vor dem roten Personenwagen auf der Überholspur fahrenden grauen Personenwagen an und fuhr an diesem vorbei, bevor er anschliessend wieder von der Normalspur vor den grauen Personenwagen auf die Überholspur wechselte.
Aufgrund dieses Vorfalls sprach das Kantonsgericht Basel-Landschaft A._ mit Entscheid vom 24. Juli 2018 der mehrfachen einfachen Verletzung von Verkehrsregeln schuldig und verurteilte ihn zu einer Busse von Fr. 300.--. Dieser Entscheid erwuchs in Rechtskraft.
Mit Verfügung vom 12. März 2019 entzog die Motorfahrzeugkontrolle des Kantons Solothurn A._ den Führerausweis für die Dauer von vier Monaten. Die dagegen von A._ erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn am 4. Juni 2019 ab.
B.
Mit Eingabe vom 21. August 2019 führt A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht. Er beantragt, das Urteil des Verwaltungsgerichts vom 4. Juni 2019 sei aufzuheben. Stattdessen sei die Dauer des Führerausweisentzugs auf einen Monat ab Einsendung des Führerausweises festzulegen. Gebühren seien keine zu erheben. Im Übrigen sei die Sache zur Regelung der Einzugsmodalitäten an die Vorinstanz, eventualiter an die Motorfahrzeugkontrolle zurückzuweisen. Eventualiter sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Motorfahrzeugkontrolle sowie das Bundesamt für Strassen beantragen ebenfalls, die Beschwerde abzuweisen.
C.
Mit Präsidialverfügung vom 24. September 2019 hat der Präsident der I. öffentlich-rechtlichen Abteilung das Gesuch des Beschwerdeführers um aufschiebende Wirkung gutgeheissen.

Erwägungen:
1.
Angefochten ist ein kantonal letztinstanzlicher Endentscheid über einen Führerausweisentzug. Dagegen steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> offen. Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde einzutreten.
2.
Streitig ist, ob die Vorinstanz das Verhalten des Beschwerdeführers zu Recht als mittelschwere Widerhandlung im Sinne von <ref-law>erachtete.
2.1. Das Gesetz unterscheidet zwischen der leichten, mittelschweren und schweren Widerhandlung (Art. 16a-c SVG). Gemäss <ref-law> begeht eine leichte Widerhandlung, wer durch Verletzung von Verkehrsregeln eine geringe Gefahr für die Sicherheit anderer hervorruft, sofern ihn dabei nur ein leichtes Verschulden trifft (Abs. 1 lit. a). Eine mittelschwere Widerhandlung begeht, wer durch Verletzung von Verkehrsregeln eine Gefahr für die Sicherheit anderer hervorruft oder in Kauf nimmt (<ref-law>). Nach einer mittelschweren Widerhandlung wird der Führerausweis für mindestens einen Monat entzogen (Abs. 2 lit. a). Leichte und mittelschwere Widerhandlungen werden von <ref-law> als einfache Verkehrsregelverletzungen erfasst (<ref-ruling>E 2.4 S. 143 f.). Die mittelschwere Widerhandlung nach <ref-law> stellt einen Auffangtatbestand dar. Sie liegt vor, wenn nicht alle privilegierenden Elemente einer leichten Widerhandlung nach <ref-law> und nicht alle qualifizierenden Elemente einer schweren Widerhandlung nach <ref-law> gegeben sind. Die Annahme einer schweren Widerhandlung setzt kumulativ eine qualifizierte objektive Gefährdung und ein qualifiziertes Verschulden voraus. Ist die Gefährdung gering, aber das Verschulden hoch, oder umgekehrt die Gefährdung hoch und das Verschulden gering, liegt eine mittelschwere Widerhandlung vor (vgl. zum Ganzen: <ref-ruling>E. 3.2 S. 452; Urteil 1C_453/2018 vom 22. August 2019 E. 3.1; je mit Hinweisen). Gleiches gilt bei einer mittelgrossen Gefährdung und einem mittelschweren oder schweren Verschulden (vgl. BERNHARD RÜTSCHE/DENISE WEBER, in: Basler Kommentar, SVG, 2014, N. 13 zu <ref-law>). Eine Gefahr für die Sicherheit anderer im Sinne von Art. 16a-c SVG ist bei einer konkreten oder auch bei einer erhöhten abstrakten Gefährdung zu bejahen. Eine erhöhte abstrakte Gefahr besteht, wenn die Möglichkeit einer konkreten Gefährdung oder Verletzung naheliegt. Ob eine solche Gefährdung vorliegt, ist anhand der jeweiligen Verhältnisse im Einzelfall zu beurteilen (vgl. Urteil 1C_634/2017 vom 10. April 2018 E. 5.1 mit Hinweis).
2.2. Aus <ref-law> wird das Verbot des Rechtsüberholens abgeleitet. Hierbei handelt es sich um eine für die Verkehrssicherheit objektiv wichtige Vorschrift, deren Missachtung eine erhebliche Gefährdung der Verkehrssicherheit nach sich zieht und daher objektiv schwer wiegt. Wer auf der Autobahn fährt, muss sich darauf verlassen können, dass er nicht plötzlich rechts überholt wird. Das Rechtsüberholen auf der Autobahn, wo hohe Geschwindigkeiten gefahren werden, stellt eine erhöhte abstrakte Gefährdung dar (<ref-ruling> E. 3.2 S. 96 f.; Urteil 6B_208/2019 vom 13. September 2019 E. 1.2.1; je mit Hinweisen).
Überholen liegt vor, wenn ein schnelleres Fahrzeug ein in gleicher Richtung langsamer vorausfahrendes einholt, an ihm vorbeifährt und vor ihm die Fahrt fortsetzt, wobei weder das Ausschwenken noch das Wiedereinbiegen eine notwendige Voraussetzung des Überholens bildet (<ref-ruling> E. 3.2 S. 97; Urteil 6B_208/2019 vom 13. September 2019 E. 1.2.1; je mit Hinweisen).
Eine Ausnahme vom Verbot des Rechtsüberholens sieht Art. 8 Abs. 3 Satz 1der Verkehrsregelnverordnung vom 13. November 1962 (VRV; SR 741.11) allgemein und Art. 36 Abs. 5 lit. a VRV für Autobahnen "beim Fahren in parallelen Kolonnen" vor. Gestattet ist, rechts an anderen Fahrzeugen unter Wechsel des Fahrstreifens vorbeizufahren (sog. Vorfahren), wenn dies ohne Behinderung des übrigen Verkehrs möglich ist (vgl. <ref-law>; <ref-ruling> E. 3.3; <ref-ruling> E. 4 S. 59; je mit Hinweisen). Das Rechtsüberholen durch Ausschwenken und Wiedereinbiegen ist hingegen gemäss Art. 8 Abs. 3 Satz 2 VRV ausdrücklich untersagt. Beim Fahren in parallelen Kolonnen auf Autobahnen darf deshalb in keinem Fall durch Ausschwenken und Wiedereinbiegen rechts überholt werden. Dies ist namentlich der Fall, wenn ein Fahrzeuglenker die Lücken in den parallelen Kolonnen ausnützt, um auf der rechten Fahrbahn zu überholen. Nach der Rechtsprechung setzt paralleler Kolonnenverkehr dichten Verkehr auf beiden Fahrspuren, somit ein längeres Nebeneinanderfahren von mehreren sich in gleicher Richtung bewegenden Fahrzeugreihen voraus (<ref-ruling> E. 3.3; <ref-ruling> E. 3a S. 222; Urteil 6B_208/2019 vom 13. September 2019 E. 1.2.1; je mit Hinweisen). Kolonnenverkehr ist anhand der konkreten Verkehrssituation zu bestimmen und zu bejahen, wenn es auf der (linken und/oder mittleren) Überholspur zu einer derartigen Verkehrsverdichtung kommt, dass die auf der Überhol- und der Normalspur gefahrenen Geschwindigkeiten annähernd gleich sind (<ref-ruling> E. 4.2.1).
3.
3.1. Ein Strafurteil vermag die Verwaltungsbehörde grundsätzlich nicht zu binden. Allerdings gebietet der Grundsatz der Einheit der Rechtsordnung, widersprüchliche Entscheide im Rahmen des Möglichen zu vermeiden, weshalb die Verwaltungsbehörde beim Entscheid über die Massnahme von den tatsächlichen Feststellungen des Strafrichters nur abweichen darf, wenn sie Tatsachen feststellt und ihrem Entscheid zugrunde legt, die dem Strafrichter unbekannt waren, wenn sie zusätzliche Beweise erhebt oder wenn der Strafrichter bei der Rechtsanwendung auf den Sachverhalt nicht alle Rechtsfragen abgeklärt hat (vgl. <ref-ruling> E. 3.2 S. 101 f. mit Hinweisen). In der rechtlichen Würdigung des Sachverhalts - namentlich auch des Verschuldens - ist die Verwaltungsbehörde demgegenüber frei, ausser die rechtliche Qualifikation hängt stark von der Würdigung von Tatsachen ab, die der Strafrichter besser kennt, etwa weil er den Beschuldigten persönlich einvernommen hat. Auch in diesem Zusammenhang hat sie jedoch den eingangs genannten Grundsatz, widersprüchliche Urteile zu vermeiden, gebührend zu berücksichtigen (vgl. <ref-ruling> E. 3.1 S. 451; Urteil 1C_453/2018 vom 22. August 2019 E. 2.1; je mit Hinweisen).
3.2. Vorliegend ist grundsätzlich nicht bestritten, dass der Beschwerdeführer rechts überholt hat. Er stellt sich aber auf den Standpunkt, es liege lediglich eine leichte Widerhandlung im Sinne von <ref-law> und keine mittelschwere Widerhandlung nach <ref-law> vor. Er bestreitet insbesondere das Vorliegen einer erhöhten abstrakten Gefährdung respektive einer konkreten Gefahr. Er bringt vor, damit ihm eine mittelschwere Widerhandlung im Sinne von <ref-law> vorgeworfen werden könnte, hätte er durch sein Rechtsüberholmanöver eine Gefahr für die Sicherheit anderer hervorrufen oder in Kauf nehmen müssen. Dies habe das Kantonsgericht mit Urteil vom 24. Juli 2018 im Strafverfahren aber verneint. Es habe festgehalten, zu keinem Zeitpunkt habe eine konkrete Gefährdung anderer Verkehrsteilnehmer bestanden oder aussergewöhnliche äusserliche Umstände vorgelegen. Die gegenteilige Feststellung der Vorinstanz widerspreche den sachverhaltlichen Erwägungen des Kantonsgerichts. Da er lediglich eine geringe (abstrakte) Gefahr für die Sicherheit anderer hervorgerufen habe, könne ihm nur eine leichte Widerhandlung im Sinne von <ref-law> vorgeworfen werden.
3.3. Die Vorinstanz hat dazu erwogen, beim zu beurteilenden Fahrmanöver handle es sich um ein verbotenes (klassisches) Rechtsüberholen. Der Beschwerdeführer habe zunächst auf die Normalspur ausgeschwenkt und sei nach dem Überholen zweier Fahrzeuge unmittelbar vor dem grauen Personenwagen wieder auf die Überholspur eingebogen. Das vom verbotenen Rechtsüberholen zu differenzierende, erlaubte Rechtsvorbeifahren falle damit ausser Betracht, zumal es bereits am parallelen Kolonnenverkehr fehle. Die Verletzung des Verbots des Rechtsüberholens sei geeignet, mindestens eine erhöhte abstrakte Gefährdung der Verkehrsteilnehmer zu schaffen, was im Übrigen auch das Kantonsgericht in seinem Urteil vom 24. Juli 2018 festgehalten habe. Der Beschwerdeführer habe vorliegend jederzeit damit rechnen müssen, dass die überholten Fahrzeuglenker, die sich - wie auf den Videoaufnahmen ersichtlich sei - bereits längere Zeit auf der Überholspur befunden hätten, auf die rechte Spur hätten wechseln können. Mit Blick auf das erhöhte Verkehrsaufkommen und der relativ hohen, auf Autobahnen üblichen Geschwindigkeit habe der Beschwerdeführer durch sein Rechtsüberholmanöver eine ernstliche Gefahr für die Sicherheit anderer hervorgerufen. Die Motorfahrzeugkontrolle habe sein Verhalten unter diesen Umständen zu Recht nicht mehr als leicht eingestuft.
3.4. Diese Ausführungen der Vorinstanz sind im Ergebnis nicht zu beanstanden. Sie hat gestützt auf die tatsächlichen Feststellungen berechtigterweise auf eine mittelschwere Widerhandlung geschlossen. Aus dem Umstand, dass der Beschwerdeführer vom Kantonsgericht nur wegen einer einfachen Verkehrsregelverletzung verurteilt wurde, kann nicht darauf geschlossen werden, es liege bloss eine leichte Widerhandlung im Sinne von <ref-law> vor. Wie bereits erwähnt (vgl. E. 2.1 hiervor) entspricht eine einfache Verkehrsregelverletzung im Sinne von <ref-law> sowohl einer leichten als auch einer mittelschweren Widerhandlung. Unzutreffend ist insofern der Einwand des Beschwerdeführers, in einem Falle von <ref-law> könne nie eine mittelschwere Widerhandlung gemäss <ref-law> vorliegen, jedenfalls nicht in der Variante einer Inkaufnahme einer ernstlichen Gefahr für die Sicherheit anderer, da dies ausdrücklich entweder eine konkrete Gefahr für die Sicherheit anderer oder deren Inkaufnahme voraussetze.
Wenn die Vorinstanz anhand der Videoaufzeichnungen erwogen hat, es habe kein Kolonnenverkehr geherrscht und es liege kein (passives) Rechtsvorbeifahren vor, ist darin weder eine offensichtlich unrichtige Sachverhaltsfeststellung erkennbar noch eine Bundesrechtsverletzung. Was der Beschwerdeführer dagegen einwendet, insbesondere seine Behauptung, die Geschwindigkeit sei auf beiden Spuren annähernd gleich gewesen und er habe keine konkrete Gefahr geschaffen, ändert daran nichts. Entgegen seiner Auffassung hat er durch sein Fahrmanöver eine erhöhte abstrakte Gefährdung anderer Verkehrsteilnehmer hervorgerufen bzw. in Kauf genommen. Gemäss dem grundsätzlich unbestrittenen Sachverhalt ist der Beschwerdeführer mehrfach ausgeschwenkt und wieder eingebogen. Da das Bundesgericht im vom Beschwerdeführer zitierten Entscheid <ref-ruling> an seiner Rechtsprechung, wonach das Rechtsüberholen durch Ausschwenken und Wiedereinbiegen gemäss Art. 8 Abs. 3 VRV auch beim Fahren in parallelen Kolonnen ausdrücklich untersagt ist, festgehalten hat, kann er indessen auch aus diesem Entscheid nichts zu seinen Gunsten ableiten.
Schliesslich überzeugt auch nicht, wenn der Beschwerdeführer vorbringt, das Kantonsgericht habe festgehalten, es liege kein klassisches Rechtsüberholen vor. Zwar trifft es zu, dass das Kantonsgericht im Zusammenhang mit der Frage, ob ein geradezu rücksichtsloses oder sonst schwerwiegend verkehrswidriges Verhalten im Sinne von <ref-law> vorliege, ausgeführt hat, die Fahrweise des Beschwerdeführers stelle kein klassisches Überholmanöver dar. Zuvor erwog es hingegen, das zu beurteilende rechtsseitige Passieren des roten und grauen Fahrzeugs sowie das anschliessende Wiedereinbiegen auf die Überholspur stelle ein klassisches Rechtsüberholen dar und sei klarerweise als verboten zu qualifizieren. Ein ähnliches Fahrmanöver wie dasjenige, welches dem Beschwerdeführer vorgeworfen wird, hat das Bundesgericht im Urteil 6B_210/2014 vom 28. Juli 2014 ebenfalls als klassisches verbotenes Rechtsüberholen gewertet (vgl. den Hinweis in: <ref-ruling> E. 5.1 S. 102). Daran ist festzuhalten.
3.5. Bei der vorliegenden konkreten Verkehrssituation, d.h. vor dem Hintergrund, dass der Vorfall auf einer Autobahn stattfand, wo aufgrund der erhöhten Geschwindigkeiten bei einem Rechtsüberholen gemäss ständiger bundesgerichtlicher Rechtsprechung per se von einer naheliegenden Möglichkeiten einer konkreten Gefährdung oder Verletzung bzw. von der Schaffung einer erhöhten abstrakten Gefahr für die Sicherheit anderer auszugehen ist (vgl. E. 2.2 hiervor), hat die Vorinstanz das Verhalten des Beschwerdeführers zu Recht als mittelschwere Widerhandlung gewertet. Der Entzug des Führerausweises des Beschwerdeführers für vier Monate, da diesem in den vergangenen zwei Jahren der Ausweis bereits einmal wegen einer schweren Widerhandlung entzogen worden war (<ref-law>), verletzt demzufolge kein Bundesrecht.
4.
4.1. Der Beschwerdeführer rügt weiter, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör verletzt, indem sie festgehalten habe, es sei keine detaillierte Begründung der erstinstanzlich festgelegten Gerichtsgebühr in der Höhe von Fr. 584.45 geboten gewesen.
4.2. Nach der bundesgerichtlichen Praxis zum Anspruch auf rechtliches Gehör im Sinne von <ref-law> muss ein Kosten- und Entschädigungsentscheid unter Umständen gar nicht begründet werden oder kann eine äusserst knappe Begründung genügen. Dies gilt insbesondere, wenn es um Kosten geht, die nach Massgabe der einschlägigen kantonalen Bestimmungen pauschal, innerhalb eines gewissen Rahmentarifs, erhoben werden können, was eine gewisse Schematisierung erlaubt. In diesem Fall wird eine besondere Begründung nur verlangt, wenn der Rahmen über- oder unterschritten wird oder die Parteien besondere Umstände geltend machen (vgl. <ref-ruling> E. 5.1 S. 504; Urteil 1B_328/2019 vom 17. Juli 2019 E. 4.1; je mit Hinweisen).
4.3. Vorliegend ist nicht zu beanstanden, wenn die Vorinstanz festgehalten hat, die fast vollständige Ausschöpfung des in § 44novies der kantonalen Verordnung über Steuern und Gebühren für Motorfahrzeuge, Fahrräder und Schiffe vom 1. Oktober 1962 (BGS 614.62) normierten Kostenrahmens erscheine als angemessen. Gemäss § 3 des kantonalen Gebührentarifs vom 24. Oktober 1979 (BGS 615.11) sind die Gebühren innerhalb eines Gebührenrahmens nach dem Zeit- und Arbeitsaufwand, nach der Bedeutung des Geschäftes, nach dem Interesse an der Verrichtung sowie nach der wirtschaftlichen Leistungsfähigkeit des Gebührenpflichtigen zu bemessen. Der Beschwerdeführer macht keine besonderen Umstände geltend, weshalb ausnahmsweise eine besondere Begründung zu verlangen wäre. Zwar hält sich die Gebühr mit Fr. 584.45 am Ende des der Administrativbehörde zur Verfügung stehenden Rahmens von Fr. 30.-- bis Fr. 600.-- (vgl. § 44novies der Verordnung über Steuern und Gebühren für Motorfahrzeuge, Fahrräder und Schiffe). Für die Verfügung, welche vier Seiten umfasst und aufgrund des vorgängig durchgeführten Schriftenwechsels, erscheint die Gebühr indessen weder übersetzt noch willkürlich.
4.4. Ebenfalls unbehelflich ist die Rüge des Beschwerdeführers, wonach § 3 des Gebührentarifs keine hinreichende gesetzliche Grundlage bilde, da es dieser Bestimmung an der Fixierung eines gesetzlichen Gebührenmaximums fehle. Die Erhebung einer Gebühr sei daher grundsätzlich unzulässig, weil sie ohne genügende gesetzliche Grundlage in die Eigentumsgarantie des Beschwerdeführers eingreife.
Mit § 44novies der Verordnung über Steuern und Gebühren für Motorfahrzeuge, Fahrräder und Schiffe liegt eine ausreichende gesetzliche Grundlage für die Erhebung der vorliegend umstrittenen Gebühr vor. Eine Parlamentsverordnung kann nämlich die Funktion eines formellen Gesetzes erfüllen, wenn die kantonale Verfassung in der betreffenden Materie die abschliessende Zuständigkeit des Parlaments vorsieht oder dafür Raum lässt (vgl. Urteil 1B_328/2019 vom 17. Juli 2019 E. 4.2 mit Hinweis). Die Verfassung des Kantons Solothurn vom 8. Juni 1986 (KV/SO; BSG 131.221) sieht in Art. 71 KV/SO vor, dass der Kantonsrat alle grundlegenden und wichtigen Bestimmungen in Form des Gesetzes (Abs. 1) und Einführungsvorschriften zu Bundesgesetzen und Bundesbeschlüssen in Form der Verordnung (Abs. 2) erlässt. § 371 Abs. 1 des kantonalen Gesetzes über die Einführung des Schweizerischen Zivilgesetzbuches vom 4. April 1954 (BGS 211.1) hält sodann fest, dass der Kantonsrat im Gebührentarif die von den administrativen und richterlichen Behörden zu erhebenden Gebühren und Kostenansätze (...) bestimmt. § 3 des Gebührentarifs legt in den Grundsätzen die Bemessungsfaktoren fest, welche bei der Berechnung der Gebühren zu beachten sind. Konkretisiert wird der Gebührenrahmen sodann im vorliegend einschlägigen § 44novies der Verordnung über Steuern und Gebühren für Motorfahrzeuge, Fahrräder und Schiffe, welcher für Administrativverfahren den bereits erwähnten Kostenrahmen von Fr. 30.-- bis 600.-- vorsieht. Damit ist die Gesetzmässigkeit des Kostenentscheids der Motorfahrzeugkontrolle, welcher von der Vorinstanz gestützt wurde, erstellt.
5.
Die Beschwerde erweist sich als unbegründet und ist abzuweisen. Bei diesem Verfahrensausgang wird der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird dem Beschwerdeführer, dem Bau- und Justizdepartement des Kantons Solothurn, dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Strassen Sekretariat Administrativmassnahmen schriftlich mitgeteilt.
Lausanne, 20. Dezember 2019
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Sauthier